[PS]#Bear and Steady Gene

 

---

 

https://www.hackerrank.com/challenges/bear-and-steady-gene/problem

Bear and Steady Gene | HackerRank

 

#include <bits/stdc++.h> 
using namespace std; 
int origin[4], mmm[4], n = 0, sz = 0, answer = INT_MAX; 
char sss[4] = { 'A', 'C', 'G', 'T' }; 
void SetCount(int val[], char c, bool sign) 
{ 
	for (int i = 0; i < 4; ++i) 
	{ 
		if (sss[i] == c) { (sign) ? val[i]++ : val[i]--; break; } 
	} 
} 
bool Check(int val[]) 
{ 
	for (int i = 0; i < 4; ++i) 
	{ 
		if (mmm[i] == 0) continue; 
		if (val[i] < mmm[i]) return false; 
	} 
	return true; 
} 
int steadyGene(string gene) 
{ 
	n = gene.size(); 
	sz = n / 4; 
	for (int j = 0; j < n; ++j) 
	{ 
		for (int i = 0; i < 4; ++i) 
		{ 
			if (gene[j] == sss[i]) 
			{ 
				origin[i]++; 
				break; 
			} 
		} 
	} 
	bool allPass = true; 
	for (int i = 0; i < 4; ++i) 
	{ 
		mmm[i] = origin[i] - sz; 
		if (mmm[i] <= 0) { mmm[i] = 0; continue; } 
		allPass = false; 
	} 
	if (allPass) return 0; 
	int calc[4] = { 0, }, ffIdx = 0; 
	for (int j = 0; j < n; ++j) 
	{ 
		SetCount(calc, gene[j], true); 
		if (Check(calc) == false) continue; 
		while (ffIdx <= j) 
		{ 
			answer = min(answer, j - ffIdx + 1); 
			SetCount(calc, gene[ffIdx], false); 
			ffIdx++; 
			if (Check(calc) == false) break; 
		} 
	} 
	return answer; 
}

 

 

* 문제 풀이 과정

 

문제에서 말하는 4 가지의 문자 A,C,G,T 가 문자열의 길이 n 에서 n / 4 Time 만큼 등장해야한다고 되어있다.

이 때, 바꿀 수 있는 부분 문자열의 최소 길이를 구하라는 문제이다.

 

핵심은 n / 4 번보다 추가되는 문자가 포함된 부분문자열을 찾으면 된다.

이 부분문자열은 A,C,G,T 가 n/4 번 나오게 무조건 만들 수 있는가 ??

단지 추가되는 문자만 부족한 문자로 바꿔주는 작업이기에 가능하다.

 

1. 문자열을 추가하면서 부족한 문자열이 포함되어있는지 확인한다.

2. 앞 문자를 지워가며 부족한 문자열이 포함되있는 조건을 만족하는지 확인하며

해당 부분문자열의 최솟값을 구한다.

 

예외적인 상황으로는,

A,C,G,T 가 n/4 번이 나오는 정상적인 문자열이 들어올 수 있기 때문에 확인해주어야한다.