[Java] 백준 15831번 : 준표의 조약돌

1. 문제

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

 

2. 접근 방법

1. 준표는 까만색을 싫어하고 , 흰색 돌은 좋아한다. 최대가 B까지 정해져있고, 최소 W만큼 조약돌을 주어야 한다.
2. 브루트포스로 가능하지만 N값이 30만으로 O(N^2) 시간초과가 발생한다.
3. 따라서 투포인터를 생각하였고, 포인터를 넘어가며 B 조약돌이 최대를 넘으면 최대경계선 까지 포인터를 옮겨주어야 한다.(코드를 보는것이 이해가 더 빠를 것이다.)

 

3. 코드

      

      

      

    
    

      <java />
    
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N,B,W;
    private static char[] arr;
    private static int max = Integer.MIN_VALUE;


    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        arr = new char[N];

        String line = br.readLine();
        for(int i = 0 ; i < line.length() ; i++){
            arr[i] = line.charAt(i);
        }
    }

    //실행
    public static void process() {
        int s = 0;
        int e = 0;

        int wCount = 0;
        int bCount = 0;

        while(e<N){
            if(arr[e] == 'W'){
                wCount++;
                e++;
            }else{
                bCount++;
                
                //검정 조약돌이 최대 B를 넘어간다면 검정 조약돌을 줄여야한다.
                //즉 포인터s를 옮기며 조약돌 갯수를 체크한다.
                while(bCount>B){
                    if(arr[s] =='W'){
                        wCount--;
                    }else{
                        bCount--;
                    }
                    s++;
                }

                e++;
            }
            if(wCount>=W){
                max = Math.max(max,e-s);
            }
        }

        if(max == Integer.MIN_VALUE){
            System.out.println(0);
        }else{
            System.out.println(max);
        }
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}