[백준] 12891번 - DNA 비밀번호 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 문자열에 대해 고정된 길이의 임의의 구간이 비밀번호의 조건을 만족하는 경우의 수를 구하는 문제다. 조건은 구간이 각 문자를 특정 개수 이상 포함해야 한다. 문자열과 구간의 최대 길이가 $1,000,000$ 이라는 점에서 $O(N^2)$ 풀이는 시간 초과가 발생하는데 슬라이딩 윈도우를 활용하면 해결할 수 있다.

슬라이딩 윈도우는 $P$ 만큼의 초기 윈도우를 설정한 후 한 칸씩 이동하며 포함된 문자를 더하고 빼는 과정과 수를 세는 과정을 반복하면 된다.

---

2. 코드

1. 슬라이딩 윈도우 [Java]

특정 문자를 포함하는 조건은 카운팅 배열을 활용해서 찾되 문자가 인덱스에 바로 매핑이 안되기 때문에 Map 을 활용해서 미리 매핑을 지어줬다.

import java.io.*;
import java.util.*;

public class Main {

    // 알파벳과 인덱스 매핑
    static Map<Character, Integer> map = Map.of(
            'A', 0,
            'C', 1,
            'G', 2,
            'T', 3
    );

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        char[] str = br.readLine().toCharArray();

        int[] cntArr = new int[4];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            cntArr[i] = Integer.parseInt(st.nextToken());
        }

        // 만들 수 있는 비밀번호의 종류의 수
        int cnt = 0;

        // 초기 윈도우에 대해 카운팅 배열 갱신
        for (int i = 0; i < P; i++) {
            cntArr[map.get(str[i])]--;
        }

        // 초기 윈도우로 만들 수 있는 비밀번호면 카운팅
        if (isPossible(cntArr)) {
            cnt++;
        }

        for (int i = 0; i < S - P; i++) {
            // 윈도우 이동
            cntArr[map.get(str[i])]++;
            cntArr[map.get(str[i + P])]--;

            // 이동 후 만들 수 있는 비밀번호면 카운팅
            if (isPossible(cntArr)) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }

    static boolean isPossible(int[] arr) {
        for (int n : arr) {
            if (n > 0) return false;
        }
        return true;
    }
}

2. 슬라이딩 윈도우 [C++]

특정 문자를 포함하는 조건은 카운팅 배열을 활용해서 찾되 문자가 인덱스에 바로 매핑이 안되기 때문에 매핑용 배열을 활용해서 미리 매핑을 지어줬다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int slen, plen;
    string s;
    cin >> slen >> plen >> s;

    vector<int> cntArr(4);
    for (int& x : cntArr) cin >> x;

    // 알파벳과 인덱스 매핑
    int mp[128];
    mp['A'] = 0;
    mp['C'] = 1;
    mp['G'] = 2;
    mp['T'] = 3;

    // 만들 수 있는 비밀번호의 종류의 수
    int cnt = 0;

    // 초기 윈도우에 대해 카운팅 배열 갱신
    for (int i = 0; i < plen; i++) {
        cntArr[mp[s[i]]]--;
    }

    // 초기 윈도우로 만들 수 있는 비밀번호면 카운팅
    if (*max_element(cntArr.begin(), cntArr.end()) <= 0) {
        cnt++;
    }

    for (int i = 0; i < slen - plen; i++) {
        // 윈도우 이동
        cntArr[mp[s[i]]]++;
        cntArr[mp[s[i + plen]]]--;

        // 이동 후 만들 수 있는 비밀번호면 카운팅
        if (*max_element(cntArr.begin(), cntArr.end()) <= 0) {
            cnt++;
        }
    }

    cout << cnt;
}

---

3. 풀이 정보

1. 슬라이딩 윈도우 [Java]

언어	시간	메모리	코드 길이
Java 11	328 ms	22000 KB	1658 B

2. 슬라이딩 윈도우 [C++]

언어	시간	메모리	코드 길이
C++ 17	4 ms	3680 KB	1043 B

---