[백준] 준표의 조약돌

✔️ 문제

• 문제 링크 : https://www.acmicpc.net/problem/15831

✔️ 문제 요약과 이해

• 검은 조약돌과 흰 조약돌이 일렬로 놓아져 있다.
• 검은색 조약돌은 B개 이하, 흰색 조약돌은 W개 이상 포함하는 가장 긴 연속된 구간의 길이를 출력해라.

✔️ 풀이

• 투 포인터를 사용해서 조건을 만족하는 가장 긴 연속된 구간을 찾아야 한다.
• 흰색 조약돌이 W개 미만이라면, 구간의 길이를 증가 시켜, 흰색 조약돌을 포함하려는 시도를 한다.
• 검은색 조약돌이 B개 초과라면, 구간의 길이를 감소 시켜, 검은색 조약돌을 미포함하려는 시도를 한다.
• 검은색 조약돌은 B개 이하, 흰색 조약돌은 W개 이상 포함하는 가장 긴 연속된 구간이라면, 구간의 길이를 증가 시켜 가장 긴 연속된 구간을 찾는 시도를 한다.

👨🏻‍💻 소스 코드

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main() {
	int ret = 0;
	int n, b, w;
	string str;

	cin >> n >> b >> w;
	cin >> str;

	int start = 0, end = 0;
	int blackCnt = 0, whiteCnt = 0;

	while (1) {
		if (blackCnt <= b && whiteCnt >= w) { // 조건을 만족하는 경우, 구간을 늘려본다. (가장 긴 구간을 찾고 있기 때문)
			ret = max(ret, end - start);
			if (str[end] == 'B')
				blackCnt++;
			else if (str[end] == 'W')
				whiteCnt++;
			end++;
		}
		else if(blackCnt > b){ // 검은돌이 조건보다 많다면, 구간을 줄여본다. 
			if (str[start] == 'B')
				blackCnt--;
			else if (str[start] == 'W')
				whiteCnt--;
			start++;
		}
		else if (whiteCnt < w) { // 흰돌이 조건보다 적다면, 구간을 늘려본다.
			if (str[end] == 'B')
				blackCnt++;
			else if (str[end] == 'W')
				whiteCnt++;
			end++;
		}

		if (end > n) break; // end 포인터가 배열 범위를 초과하는경우 구간 탐색을 중지한다.
	}

	cout << ret;

	return 0;
}

✔️ 문제 회고

• 투 포인터는 일정 조건에 부합하는 연속된 구간을 찾는데에 쓰인다.
• 가장 긴 연속된 구간을 찾을 수도 있고
• 가장 짧은 연속된 구간을 찾을 수도 있다.
• 가장 긴 연속된 구간을 찾는 경우에는 현재 구간이 조건에 부합하더라도, 구간을 늘려보며, 더 긴 연속된 구간을 찾으려 시도 해봐야한다.
• 가장 짧은 연속된 구간을 찾는 경우에는 현재 구간이 조건에 부합하더라도, 구간을 줄여보며, 더 짧은 연속된 구간을 찾으려 시도 해봐야한다.
• 투 포인터로 구간을 찾는 작업은 주로 while문 안에서 구간 맨 앞을 가리키는 포인터와 맨 뒤를 가리키는 포인터를 조건에 따라 조작하면서 이루어진다.
• 구간의 맨 뒤를 가리키는 포인터 end가 구간 탐색 대상인 전체 배열의 인덱스를 넘어서는 접근을 하게되면, break문으로 탐색을 중지해줘야 한다.