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