백준 12891 DNA 비밀번호

문제

DNA 문자열을 가지고 만들 수 있는 비밀번호의 종류의 수를 구하는 문제이다. DNA 문자열은 모든 문자열에 등장하는 문자가 A, C, G, T인 문자열을 의미한다. 또한 일정 길이의 DNA 문자열과 A, C, G, T가 각각 가져야 하는 문자열의 개수를 세봤을 때 이보다 이상이어야 성립한다. 어차피 비밀번호로 사용할 부분문자열의 길이는 주어져있고, 문자열에서 임의로 뽑아내는 것이 아닌 이어져 있는 문자열이기 때문에 슬라이딩 윈도우를 통해 풀면 될 것 같다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const [s, p] = inputs[0].split(" ").map(Number);
const str = inputs[1];
const [A, C, G, T] = inputs[2].split(" ").map(Number);
let result = 0;
for (let i = 0; i <= s - p; i++) {
  let a = A;
  let c = C;
  let g = G;
  let t = T;
  const partition = Array.from(str.slice(i, i + p));
  partition.forEach((char) => {
    if (char === "A") a--;
    else if (char === "C") c--;
    else if (char === "G") g--;
    else if (char === "T") t--;
  });
  if (a <= 0 && c <= 0 && g <= 0 && t <= 0) result++;
}
console.log(result);
 

처음에는 switch - case문을 사용해 풀었지만 메모리 초과가 나와서 if문으로 바꿨는데도 역시 났다. 사실 switch case문과는 솔직히 별 시간 차이가 나지 않을 것 같긴 해서 다른 곳이 문제라는 건데..

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const [s, p] = inputs[0].split(" ").map(Number);
const str = inputs[1];
const [a, c, g, t] = inputs[2].split(" ").map(Number);
const testSum = a + c + g + t;
const regex = new RegExp(
  `^(?=(?:[^A]*A){${a}})(?=(?:[^C]*C){${c}})(?=(?:[^G]*G){${g}})(?=(?:[^T]*T){${t}}).*$`
);
 
if (testSum > s) {
  console.log(0);
} else {
  let result = 0;
  for (let i = 0; i <= s - p; i++) {
    const testStr = str.slice(i, i + p);
    if (regex.test(testStr)) result++;
  }
  console.log(result);
}
 

킹받아서 정규표현식으로도 해봤는데 이젠 시간 초과가 뜬다

다시 생각해보니 나는 슬라이딩 윈도우를 어떻게 효율적으로 사용하는지 제대로 몰랐던 것 같다.

슬라이딩 윈도우는 일정한 크기의 윈도우를 가지고 계속 옆으로 옮겨가면서 검사를 하는 방식이지만, 이 과정에서 계속해서 변수에 새롭게 문자열을 잘라 할당하게 되면 결국 메모리 손해로 이어지고 만다. 그렇기 때문에 매번 새롭게 할당하는 방식이 아니라 기존 데이터를 일정한 크기만큼 계속 움직이는 만큼 쓸 수 있는 데이터는 그대로 쓰면서 넘어가야만 효율적인 알고리즘이 될 수 있다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const [s, p] = inputs[0].split(" ").map(Number);
const str = inputs[1];
const [a, c, g, t] = inputs[2].split(" ").map(Number);
const testSum = a + c + g + t;
 
if (testSum > s) {
  console.log(0);
  process.exit(0);
}
 
const count = { A: 0, C: 0, G: 0, T: 0 };
let result = 0;
for (let i = 0; i < p; i++) count[str[i]]++;
if (count["A"] >= a && count["C"] >= c && count["G"] >= g && count["T"] >= t)
  result++;
 
for (let i = p; i < s; i++) {
  count[str[i]]++;
  count[str[i - p]]--;
  if (count["A"] >= a && count["C"] >= c && count["G"] >= g && count["T"] >= t)
    result++;
}
 
console.log(result);
 

그렇기 때문에 객체에 기존 문자열을 모두 저장해놓고 옆으로 옮겨가면서 추가된 문자열만 하나씩 추가해주는 방식으로 바꿨더니 정답이 되었다.

앞으로 슬라이딩 윈도우를 쓸 때는 딱 그렇게만 생각하는 것이 아닌, 쓰는 방식에 대해서도 고민을 하고 코드를 작성해야 할 것 같다.