슬라이딩 윈도우를 이용한 문제 풀이 - DNA 비밀번호

* Do it 코딩테스트를 참고하였습니다. - 백준 온라인 저지 12891번

 

 슬라이딩 윈도우라는 개념은 2개의 포인터를 이용해 범위를 지정하고, 해당 범위의 크기를 유지하며 이동하면서 문제를 해결하는 방법을 뜻합니다. 전에 포스팅한 투 포인터와는 범위의 크기가 달라지지 않는다는 차이가 있지만 비슷한 부분이 존재합니다.

 

 해당 문제는 입력으로 주어지는 문자열에서 비밀번호를 만들 수 있는 조합의 개수를 찾는 문제입니다. 또다른 입력 값으로 받아지는 DNA별 필요 개수들을 확인하여 필요 개수들을 모두 만족하는 배열의 조합을 찾는 것이 문제의 포인트입니다.

 

 일정한 범위(비밀번호의 크기)를 가지는 두 포인터를 가지고 각 포인터를 한 칸씩 이동하면서 검사를 하면서 비밀번호에 추가되는, 그리고 사라지는 문자에 대한 필요 개수와 비밀번호에 존재하는 각 문자들의 개수를 비교하여 조건을 충족하는 경우에 결과값에 1을 추가하는 방식으로 탐색을 이어간다.

 

아래는 위의 내용을 통해 작성한 코드입니다.

 

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

string input; //  DNA 문자열
int N, M; // 문자열의 길이, 부분 문자열의 길이
vector<int> Count(4, 0); // ACGT가 각각 몇개 필요한지 담긴 배열
vector<int> ACGT(4, 0);  // 현재 검색중인 배열의 ACGT가 각각 몇개가 들어있는지 담긴 배열
int result = 0;
int correct = 0;

void Add(char c)
{
	int index = -1;
	switch (c)
	{
	case 'A':
		index = 0;
		break;
	case 'C':
		index = 1;
		break;
	case 'G':
		index = 2;
		break;
	case 'T':
		index = 3;
		break;
	}
	ACGT[index]++;
	if (ACGT[index] == Count[index]) correct++;
}

void Remove(char c)
{
	int index = -1;
	switch (c)
	{
	case 'A':
		index = 0;
		break;
	case 'C':
		index = 1;
		break;
	case 'G':
		index = 2;
		break;
	case 'T':
		index = 3;
		break;
	}
	if (ACGT[index] == Count[index]) correct--;
	ACGT[index]--;
}

int main()
{
	cin >> N >> M;
	cin >> input;

	for (int i = 0; i < 4; i++)
	{
		cin >> Count[i];
		if (Count[i] == 0) correct++;
	}

	for (int i = 0; i < M; i++)
	{
		Add(input[i]);
	}

    if (correct == 4)
		result++;

	for (int i = M; i < N; i++)
	{
		Add(input[i]);
		Remove(input[i - M]);

		if (correct == 4) result++;
	}

	cout << result << endl;

    return 0;
}

 

이렇게 DNA 비밀번호 문제에 대한 풀이를 마치겠습니다. 포바~!