C++ 코딩테스트 강좌, DNA 비밀번호

1. 문제 정의

얼마 전 한 생물학자가 DNA 시퀀스를 통해 특정 비밀번호를 만들어야 하는 상황에 처했습니다. 이 DNA 시퀀스는 A, C, G, T의 4종류의 뉴클레오타이드로 구성됩니다. 이 비밀번호는 주어진 DNA 시퀀스 내에서 선택된 A, C, G, T의 조합으로 만들어집니다.

문제 설명

주어진 문자열 S에서 길이가 K인 모든 부분 문자열 중에서 각 뉴클레오타이드의 빈도가 최소인 부분 문자열을 찾고, 그 중에서 비밀번호의 개수를 알아내는 프로그램을 작성하시오. 만약 모든 빈도가 같다면 그 빈도가 최소인 부분 문자열 중 가장 작은 사전 순서의 문자열을 선택합니다. 문자열의 길이는 주어진 문자열보다 작거나 같아야 합니다.

입력

첫 번째 줄에 DNA 문자열 S의 길이 N (1 ≤ N ≤ 100,000)이 주어진다.
두 번째 줄에 정수 K (1 ≤ K ≤ N)가 주어진다.
세 번째 줄에 S가 주어진다.

출력

유효한 비밀번호의 개수와 그 중 가장 작은 사전 순서의 비밀번호를 출력하시오.

2. 알고리즘 분석

이 문제를 해결하기 위해 우리는 슬라이딩 윈도우(Sliding Window) 기법을 사용할 것입니다. 이 기법은 특정 길이 K의 부분 문자열을 이동하면서 각 문자(A, C, G, T)의 빈도를 카운트하여 문제를 해결할 수 있게 해줍니다.

절차

K 길이의 첫 부분 문자열을 선택하여 문자의 빈도를 카운트한다.
이후 슬라이딩 윈도우를 사용하여 문자열을 이동하면서 새로운 문자가 추가될 때와 빠질 때 빈도를 조정한다.
각 K 길이의 문자열에서 뉴클레오타이드의 빈도를 검사하고, 가장 작은 빈도를 찾는다.
모든 문자열을 검사한 후 유효한 비밀번호의 개수와 가장 작은 사전순의 비밀번호를 출력한다.

3. C++ 코딩 예제

아래는 이 문제를 해결하기 위한 C++ 코드 예제입니다:

        #include <iostream>
        #include <string>
        #include <unordered_map>
        #include <vector>
        #include <algorithm>

        using namespace std;

        int main() {
            int N, K;
            string S;
            cin >> N >> K;
            cin >> S;

            unordered_map freq;
            for (int i = 0; i < K; i++) {
                freq[S[i]]++;
            }

            // 초기 결과 설정
            int min_freq = INT_MAX;
            vector passwords;

            // 슬라이딩 윈도우 하여 모든 K 길이 부분 문자열 검사
            for (int i = 0; i <= N - K; i++) {
                if (i > 0) {
                    freq[S[i - 1]]--;
                    freq[S[i + K - 1]]++;
                }

                // 가장 작은 빈도 찾기
                int cur_min = INT_MAX;
                for (const auto &entry : freq) {
                    cur_min = min(cur_min, entry.second);
                }

                // 유효한 비밀번호 추가
                if (cur_min <= (K / 4)) { // 모든 뉴클레오타이드의 빈도가 K/4 이하
                    passwords.push_back(S.substr(i, K));
                }
            }

            // 가장 작은 사전 순의 비밀번호 찾기
            sort(passwords.begin(), passwords.end());
            string smallest_password = (passwords.empty() ? "" : passwords[0]);
            
            // 결과 출력
            cout << passwords.size() << " " << smallest_password << endl;

            return 0;
        }

4. 코드 해설

위의 코드는 다음과 같이 작동합니다:

우선 DNA 문자열과 그 길이, 부분 문자열의 길이 K를 입력받습니다.
첫 K개의 문자의 빈도를 카운트하기 위해 unordered_map을 사용합니다.
슬라이딩 윈도우 기법을 사용하여 각 K 길이의 부분 문자열을 이동하면서 빈도를 수정합니다.
각 부분 문자열에 대해 빈도의 최소값을 계산하고, 조건에 맞는 경우에만 유효한 비밀번호 리스트에 추가합니다.
마지막에 유효한 비밀번호 리스트를 정렬하여 가장 작은 사전 순의 비밀번호를 찾습니다.

5. 테스트 케이스

이제 본 문제를 해결하기 위한 몇 가지 테스트 케이스를 살펴보겠습니다:

테스트 케이스 1

        입력:
        8 4
        ACGTTGCA

        출력:
        1 ACGT

테스트 케이스 2

        입력:
        12 5
        ACGTTACGATC

        출력:
        3 ACCTA ACTAC TCGAT

테스트 케이스 3

        입력:
        6 3
        ACGTAC

        출력:
        2 ACG ACT

6. 결론

이번 강좌에서는 DNA 비밀번호 문제를 통해 슬라이딩 윈도우 기법을 활용한 알고리즘을 배웠습니다. 이 기법은 문자열 문제를 해결하는 데 매우 유용하게 사용될 수 있으며, 다양한 변형 문제에 적용할 수 있습니다. 이를 통해 코딩 테스트에서도 채용될 수 있는 좋은 기초 지식이 될 것입니다.