설명
준표는 오랜만에 미미와 함께 산책을 나왔다. 산책로에는 일렬로 검은색과 흰색 조약돌이 놓여 있다. 총 N개의 조약돌은 1번부터 N번까지 차례로 번호가 붙여져 있다. 준표는 이 조약돌을 주워 집에 장식하려고 한다.
준표는 임의의 지점에서 산책을 시작하고, 원하는 지점에서 산책로를 빠져나와 집으로 돌아간다. 이때 준표는 산책한 구간에 있는 모든 조약돌을 줍는다. 미미의 건강을 위해 준표는 조금이라도 더 긴 구간을 산책하고 싶다. 하지만 준표에게는 확고한 취향이 있어, 아래 조건을 만족하는 구간만을 산책할 수 있다.
1.
준표는 까만색을 싫어한다. 그래서 까만색 조약돌은 B개 이하로 줍고 싶다.
2.
준표는 미미와 같은 흰색을 좋아한다. 그래서 흰색 조약돌은 W개 이상 줍고 싶다.
만약 위 조건을 만족하는 구간이 없다면 준표는 바로 집으로 돌아간다. 이때 준표와 미미가 산책할 수 있는 구간 중 가장 긴 구간의 길이를 구해보자.
입력
첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조약돌은 검은색이고, W라면 흰색이다.
출력
준표와 미미가 걷게 될 가장 긴 구간의 길이를 한 줄에 출력한다. 준표가 원하는 조건에 맞는 구간이 없다면 0을 출력한다.
예시 입력
예시 출력
10 1 2
WBBWWBWWBW
JavaScript
복사
5
JavaScript
복사
풀이 과정
문제의 핵심은 다음과 같습니다.
“까만색 조약돌을 B개 이하로 줍고 흰색 조약돌을 W개 이상 줍는 구간의 최대 길이를 구하는 문제"
rp를 움직이면서 돌 색깔에 따른 카운트 횟수를 추가하고, lp 를 움직이면서 돌 색깔에 따른 카운트 횟수를 감소합니다.
만약 카운트가 준표의 조건에 부합한다면 (즉, 까만색 조약돌은 B개 이하, 흰색 조약돌은 W개 이상) 최대 길이 값을 갱신합니다.
그렇다면 rp를 증가하고 lp를 증가하는 기준을 어떻게 잡아야 할까요?
핵심은 까만색 조약돌입니다. 흰색 조약돌은 개수에 상관없이 주울 수 있지만, 까만색 조약돌은 그 한계가 존재합니다.
따라서 까만색 조약돌을 주울 수 있는 그 최대 만큼 rp 를 증가하고, 조건에 맞지 않는다면 lp 를 증가합니다.
최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class _15831 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
int[] stones = new int[N];
String input = br.readLine();
for (int i = 0; i < N; i++) {
stones[i] = input.charAt(i) == 'B' ? 1 : 0;
}
int leftPoint = 0, rightPoint = 0, blackCount = 0, whiteCount = 0;
int max = 0;
while (rightPoint < N) {
while (blackCount > B) {
if (stones[leftPoint] == 1) {
blackCount--;
} else {
whiteCount--;
}
leftPoint++;
}
if (stones[rightPoint] == 1) {
blackCount++;
} else {
whiteCount++;
}
rightPoint++;
if (blackCount <= B && whiteCount >= W) {
max = Math.max(max, rightPoint - leftPoint);
}
}
System.out.print(max);
}
}
JavaScript
복사
