백준 12891 c++ "DNA 비밀번호" -PlusUltraCode-

https://www.acmicpc.net/problem/12891

 

 

 

[필자 사고]

 

필자의 처음 이 문제의 접근 방법은 아래와 같았다.

 

1. 해당 부분문자열 크기만큼 문자열들을 생성하여 ACGT 의 조건에 맞게 검사한다.

 

논리상으로는 문제가 없는 접근법이다.

 

다만 시간복잡도 측면에서는 문제가 생길 수 있따. N의 크기가 10^6 이므로 O(n)으로 문제를 해결해야 됬는데

필자는 부분문자열 크기만큼 계속 새로운 문자열들을 생성하였기 때문에 이 조건에 위배되어 시간초과가 발생했따.

 

그래서 해결책은 아래와 같다.

2. 이동하는 startIdx 와 endIdx 의 `문자`만 조사하여 이동하자!!

 

[소스코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>

using namespace std;

string str;
int N, M;
vector<int> ACGT(4);
int resultCount = 0;

void Input() {
	cin >> N >> M;
	cin >> str;
	for (int i = 0; i < 4; i++) {
		cin>>ACGT[i];
	}
}

int getACGTIdx(char ch) {
	if (ch == 'A') return 0;
	else if (ch == 'C') return 1;
	else if (ch == 'G')return 2;
	else if (ch == 'T') return 3;
}
void checkCount() {
	for (int i = 0; i < 4; i++) {
		if (ACGT[i] > 0)return;
	}
	resultCount++;
}

void GameStart() {
	int startIdx = 0;
	int endIdx = startIdx + M - 1;
	
	for (int i = startIdx; i <= endIdx; i++) {
		ACGT[getACGTIdx(str[i])]--;
	}

	while (endIdx < N) {
			checkCount();
			int idx = getACGTIdx(str[startIdx]);
			ACGT[idx]++;
			startIdx++;
			endIdx++;
			if (endIdx < N) {
				int idx2 = getACGTIdx(str[endIdx]);
				ACGT[idx2]--;
			}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	GameStart();
	cout << resultCount;
}