백준 15831 : 준표의 조약돌 (투포인터)

 

문제

준표는 오랜만에 미미와 함께 산책을 나왔다. 산책로에는 일렬로 검은색과 흰색 조약돌이 놓여 있다. 총 N개의 조약돌은 1번부터 N번까지 차례로 번호가 붙여져 있다. 준표는 이 조약돌을 주워 집에 장식하려고 한다.

준표는 임의의 지점에서 산책을 시작하고, 원하는 지점에서 산책로를 빠져나와 집으로 돌아간다. 이때 준표는 산책한 구간에 있는 모든 조약돌을 줍는다. 미미의 건강을 위해 준표는 조금이라도 더 긴 구간을 산책하고 싶다. 하지만 준표에게는 확고한 취향이 있어, 아래 조건을 만족하는 구간만을 산책할 수 있다.

1. 준표는 까만색을 싫어한다. 그래서 까만색 조약돌은 B개 이하로 줍고 싶다.
2. 준표는 미미와 같은 흰색을 좋아한다. 그래서 흰색 조약돌은 W개 이상 줍고 싶다.

만약 위 조건을 만족하는 구간이 없다면 준표는 바로 집으로 돌아간다. 이때 준표와 미미가 산책할 수 있는 구간 중 가장 긴 구간의 길이를 구해보자.

입력

첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조약돌은 검은색이고, W라면 흰색이다.

출력

준표와 미미가 걷게 될 가장 긴 구간의 길이를 한 줄에 출력한다. 준표가 원하는 조건에 맞는 구간이 없다면 0을 출력한다.

Small (100점)

• 1 ≤ N ≤ 3,000
• 0 ≤ B, W, B+W ≤ N

Large (150점)

• 1 ≤ N ≤ 300,000
• 0 ≤ B, W, B+W ≤ N

예제 입력 1 복사

10 1 2
WBBWWBWWBW

예제 출력 1 복사

5

예제 입력 2 복사

7 2 4
WBBBBBW

예제 출력 2 복사

0

 

 

• 풀이

 

기존 투포인터 문제와 코드는 크게 다르지 않았지만 break로 탈출하는 걸 생각하지 못해서 많이 해매다 풀이를 보고

이해했다..

 

문제에서 요구하는 조건인 흰색 돌 갯수, 검은색 돌 갯수 중에흰색은 w개 이상이 와도 되지만

검은색은 b개 이상이 올 수 없다

while 문을 쭉 진행하면서 검은색이 b개인데 다음 돌도 검은색이면 b+1개가 되니 break로 그 돌을 넣지 않은 상태로

반복문을 빠져나온다

탈출한 다음 정답이 될 수 있는지 확인하고 뒤에 돌을 더 넣기 위해서 돌을 맨 앞쪽부터 하나씩 빼면서

검은색을 b개 이하가 되게 맞춰줘야한다

 

 

 

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

class Main
{

    public static void main (String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int b = in.nextInt(); //b개 이하로
        int w = in.nextInt(); //w개 이상으로
        int tmpB = 0, tmpW = 0, res = 0, ans = 0;

        String s = in.next();
        int next = 0;

        for (int i = 0; i < n; i++){
            // 일단 B가 n개 까지 나올때까지 가본다
            while (next < n){
                if (tmpB == b && s.charAt(next) == 'B') break;
                if (s.charAt(next++) == 'W') tmpW++;
                else tmpB++;
            }

            if (tmpW >= w) ans = Math.max(ans,next - i);
            if (s.charAt(i) == 'B') tmpB--;
            else if (s.charAt(i) == 'W') tmpW--;

        }
        System.out.println(ans);
    }
}