[JavaScript] 백준 12891 DNA 비밀 번호 (JS)

DNA 비밀 번호

📚 문제 설명

{A, C, G, T} 로 이루어진 길이 S 의 문자열이 주어진다.
해당 문자열에서 P 의 길이를 가진 부분 문자열을 뽑아서 비밀 번호를 만들려고 한다.
비밀 번호를 만들기 위한 조건으로 {A, C, G, T} 가 각각 몇개 이상으로 반드시 있어야하는지 배열로 주어진다.

예를 들어 [2, 0, 0, 1] 이 주어지면 A 2개 이상, T 1개 이상이 포함되야 한다는 뜻이다.

이렇게 하여 만들 수 있는 비밀 번호의 수를 출력하라

👨🏻‍💻 풀이 과정

이 문제는 Sliding Window 알고리즘을 이용해야 한다.
해당 알고리즘을 간략하게 설명하면 다음과 같다.
1, 2, 3, 4, 5, 6 이 중에 3개의 연속된 숫자를 더하는 최대값을 찾을 때,

• 우선 (1, 2, 3), 4, 5, 6 다음과 같이 먼저 계산을 한다. 1 + 2 + 3 = 6
• 다음을 계산 할 때 원래 계산 값 6에 원래 배열의 가장 앞, 추가할 숫자를 해준다.
• 그럼 6 - 1 + 4 를 진행한다. 그럼 이 값은 1, (2, 3, 4), 5, 6 이 된다.

즉 간단히 표현하면 삭제 - 유지할 부분 - 추가 이렇게 반복하는 것이고
이렇게 계산하는 방식을 Sliding Window 알고리즘이라고 한다.

그럼 Sliding Window 알고리즘을 이용하여 로직을 생각해보자

• 0 부터 P 까지 문자열을 확인하여 해당 문자열에 {A, C, G, T} 가 각각 몇개 인지 숫자를 센다.
• 해당 문자열이 조건에 충족되면 answer 변수에 +1
• 그 후 반복문을 돌며 아래 과정 반복
• Sliding Window 알고리즘을 이용하여 다음 문자열에 {A, C, G, T} 가 각각 몇개 인지 이전 값에서 삭제되는 값과 추가할 값을 수정하여 갱신
• 조건에 충족하면 answer 변수에 + 1

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let [N, M] = input.shift().split(' ').map(Number);
    const PASSWORD = input.shift();
    const REQUIRE = input.shift().split(' ').map(Number);

	// ACGT 가 몇개 있는지 저장해줄 변수
    let passwordCondition = {};
    passwordCondition['A'] = 0;
    passwordCondition['C'] = 0;
    passwordCondition['G'] = 0;
    passwordCondition['T'] = 0;
	// 정답 갯수
    let answer = 0;
	// 조건에 충족하는지 확인 
    const CHECK = () => {
        if (passwordCondition['A'] >= REQUIRE[0] && passwordCondition['C'] >= REQUIRE[1] && passwordCondition['G'] >= REQUIRE[2] && passwordCondition['T'] >= REQUIRE[3]) {
            return true;
        }else return false;
    };
	// 첫번째 문자열을 돌며 ACGT 가 각각 몇개 있는지 갱신
    for (let i = 0; i < M; i++) {
        passwordCondition[PASSWORD[i]] += 1;
    }
	// 만약 첫번째 문자열이 조건을 충족하는지 확인
    answer = CHECK() ? answer + 1 : answer;

	// 첫번째 문자열 다음부터 Sliding Window 알고리즘을 이용하여 갯수를 새줌
    for (let i = 0; i < PASSWORD.length - M; i++) {
        passwordCondition[PASSWORD[i]] -= 1;
        passwordCondition[PASSWORD[i + M]] += 1;
        answer = CHECK() ? answer + 1 : answer;
    }
    console.log(answer);

🧐 후기

최근에 문자열 문제를 풀면서 처음 들어보는 알고리즘을 많이 보는 것 같다.
이 Sliding Window 알고리즘은 투 포인터와 비슷한 것 같지만, 투 포인터의 경우 크기가 유동적일 경우 더 유용할 것 같고 크기가 일정한 문제의 경우 Sliding Window 알고리즘이 더 유용할 것 같다.