[C++][백준] 준표의 조약돌(15831) - 투포인터
문제
준표는 오랜만에 미미와 함께 산책을 나왔다. 산책로에는 일렬로 검은색과 흰색 조약돌이 놓여 있다. 총 N개의 조약돌은 1번부터 N번까지 차례로 번호가 붙여져 있다. 준표는 이 조약돌을 주워 집에 장식하려고 한다.
준표는 임의의 지점에서 산책을 시작하고, 원하는 지점에서 산책로를 빠져나와 집으로 돌아간다. 이때 준표는 산책한 구간에 있는 모든 조약돌을 줍는다. 미미의 건강을 위해 준표는 조금이라도 더 긴 구간을 산책하고 싶다. 하지만 준표에게는 확고한 취향이 있어, 아래 조건을 만족하는 구간만을 산책할 수 있다.
- 준표는 까만색을 싫어한다. 그래서 까만색 조약돌은 B개 이하로 줍고 싶다.
- 준표는 미미와 같은 흰색을 좋아한다. 그래서 흰색 조약돌은 W개 이상 줍고 싶다.
만약 위 조건을 만족하는 구간이 없다면 준표는 바로 집으로 돌아간다. 이때 준표와 미미가 산책할 수 있는 구간 중 가장 긴 구간의 길이를 구해보자.
출력
준표와 미미가 걷게 될 가장 긴 구간의 길이를 한 줄에 출력한다. 준표가 원하는 조건에 맞는 구간이 없다면 0을 출력한다.
풀이
투포인터를 이용하여 문제를 풀이하였습니다.
투포인터 알고리즘에서는 s, e 두개의 포인터가 사용되는데
s는 시작지점, e는 끝 지점을 의미합니다.
(저는 e가 가리키는 값은 포함하지 않기 때문에 s와 e가 동일한 경우 아무것도 포함하지 않습니다.)
테스트 케이스 1번 기반으로 그림을 그려보도록 하겠습니다.
e가 가리키는 값은 포함하지 않기 때문에 현재 상태는 흰 돌 0개, 검은 돌 0개 입니다.
검은 돌이 B(1) 이하이기 때문에 포인터 e를 증가시킵니다.
현재 상태는 흰 돌 1개, 검은 돌 0개 입니다.
검은 돌이 B(1) 이하이기 때문에 포인터 e를 증가시킵니다.
현재 상태는 흰 돌 1개, 검은 돌 1개 입니다.
검은 돌이 B(1) 이하이기 때문에 포인터 e를 증가시킵니다.
현재 상태는 흰 돌 1개, 검은 돌 2개 입니다.
검은 돌이 B(1) 보다 크기 때문에 포인터 s가 가리키는 돌을 하나 빼주고 s를 증가시켜줍니다.
현재 상태는 흰 돌 0개, 검은 돌 2개 입니다.
검은 돌이 B(1) 보다 크기 때문에 포인터 s가 가리키는 돌을 하나 빼주고 s를 증가시켜줍니다.
현재 상태는 흰 돌 0개, 검은 돌 1개 입니다.
위와 같은 과정을 거치면서 갖고 있는 흰 돌의 수가 W 이상이고 검은 돌의 수가 B 이하일 때,최대 길이를 갱신해 줍니다.
저는 e가 가리키는 값은 현재 가진 돌에 포함하지 않기 때문에, e가 N이 될 때까지 위 반복문을 진행합니다.e가 N보다 커질 때 반복문을 종료합니다.
전체 코드는 아래와 같습니다.
#include <iostream>
#include <string>
using namespace std;
int main() {
int N, B, W;
string input;
cin >> N >> B >> W;
cin >> input;
int s = 0, e = 0;
int b_cnt = 0, w_cnt = 0;
int answer = 0;
while (true) {
if (w_cnt >= W && b_cnt <= B) {
if (e - s > answer) answer = e - s;
}
if (b_cnt > B) {
if (input[s] == 'W') w_cnt--;
else if (input[s] == 'B') b_cnt--;
s++;
}
else {
e++;
if (input[e - 1] == 'W') w_cnt++;
else if (input[e - 1] == 'B') b_cnt++;
}
if (e > N) break;
}
cout << answer;
return 0;
}