[G4] 백준 15831번 준표의 조약돌 C++

리뷰

 

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

수집한 조약돌 색 조건에 맞는 구간의 최대 길이를 구하는 문제

 

 

전역 변수

1. n : 조약돌의 개수를 저장할 변수
2. b : 원하는 검은 조약돌의 최대개수를 저장할 변수
3. w : 원하는 하얀 조약돌의 최소개수를 저장할 변수
4. s : 조약돌 정보를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, b, w, s값을 입력 받는다.
2. 변수 l, r을 0으로 초기화한다.
3. 변수 cb를 s[r]이 'W'라면 0으로, 아니면 1로 초기화한다.
4. 변수 cw를 s[r]이 'W'라면 1으로, 아니면 0으로 초기화한다.
5. 변수 mx를 cb <= b, cw >= w조건을 만족하면 1로, 아니면 0으로 초기화한다.
6. r을 전위증가한 값이 n보다 작을 경우를 조건으로 하는 while루프를 수행한다.
7. 만약 s[r]이 'W'라면 cw를 증가시키고, 아니라면 cb를 증가시킨다.
8. cb가 b보다 클 경우를 조건으로 하는 while루프를 수행한다.
9. s[l]이 'B'라면 cb를 감소시키고, 아니라면 cw를 감소시킨다. l을 전위증가시키며 루프를 반복한다.
10. 루프를 빠져나온 뒤 cb <= b, cw >= w조건을 만족하면 mx를 r-l+1과 비교하여 더 큰 값으로 저장한다.
11. 모든 탐색을 마친 후 mx에 저장된 값을 출력한다.

 

트러블 슈팅

1. n이 1, b, w가 모두 0이고, 조약돌이 "W"로 주어진 케이스에서 0을 반환하여 99%에서 WA를 받았다.
2. mx의 초기값을 0이 아닌 cb, cw값을 비교해 정확하게 초기화해주어 AC를 받았다.

 

참고 사항

1. 0 ≤ B, W, B+W ≤ N이므로 B, W가 0인 경우를 잘 체크해 주어야 한다.

 

정답 코드

#include<iostream>
using namespace std;

int n, b, w;
string s;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> b >> w >> s;
	int l = 0, r = 0;
	int cb = s[r] == 'W' ? 0 : 1;
	int cw = s[r] == 'W' ? 1 : 0;

	int mx = cb <= b && cw >= w ? 1 : 0;
	while (++r < n) {
		if (s[r] == 'W') ++cw;
		else ++cb;

		while (cb > b) {
			if (s[l] == 'B') --cb;
			else --cw;
			++l;
		}

		if (cb <= b && cw >= w) mx = max(mx, r - l + 1);
	}
	cout << mx;
}