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

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

15831번: 준표의 조약돌

✅ 골드 Ⅲ

 

🔶 풀이

해당 문제는 그냥 느낌대로 풀고 봤더니 알고리즘 분류가 두 포인터라고 한다. 

 

1️⃣ 검은 조약돌의 개수를 B개 이하로 줍고 싶다.

2️⃣ 하얀 조약돌의 개수를 W개 이상으로 줍고 싶다.

 

위 조건을 충족되는 가장 긴 구간의 산책로 길이를 구하면 된다.

예제 1번을 통해서 어떻게 진행되는지 살펴보겠다.

10 1 2
WBBWWBWWBW

우선 시작점과 도착점을 모두 0으로 초기화해준다.

 

1. start = 0, end = 0 // W

검은 조약돌: 0개, 하얀 조약돌: 1개로 조건에 충족되지 않음

최대 길이 갱신 X

end++

 

2. start = 0, end = 1 // WB

검은 조약돌: 1개, 하얀 조약돌: 1개로 조건에 충족되지 않음

최대 길이 갱신 X

end++

 

3. start = 0, end = 2 // WBB

검은 조약돌: 2개, 하얀 조약돌: 1개로 검은 조약돌이 1개(B)를 넘었기 때문에 시작점을 갱신해줌

start++

 

4. start = 1, end = 2 // BB

검은 조약돌: 2개, 하얀 조약돌: 0개로 검은 조약돌이 1개(B)를 넘었기 때문에 시작점을 갱신해줌

start++

 

5. start = 2, end = 2 // B

검은 조약돌: 1개, 하얀 조약돌: 0개로 조건에 충족되지 않음

최대 길이 갱신 X

end++

 

6. start = 2, end = 3 // BW

검은 조약돌: 1개, 하얀 조약돌: 1개로 조건에 충족되지 않음

최대 길이 갱신 X

end++

7. start = 2, end = 4 // BWW

검은 조약돌: 1개, 하얀 조약돌: 2개로 조건에 충족되므로 최대 길이를 3으로 갱신해줌

 

·

·

·

 

이런 식으로 산책로의 끝까지 방문해주면 된다.

 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    static long max;
    static long ans = Long.MAX_VALUE;
	
    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()); // 하얀 조약돌 최소 개수
		
        char[] road = br.readLine().toCharArray();
		
        int start = 0; // 시작점
        int end = 0;  // 도착점
		
        int blackCnt = 0; // 검은 조약돌 개수
        int whiteCnt = 0; // 하얀 조약돌 개수
        int len = 0;	  // 현재 산책로 길이
        int answer = 0;
		
        while (end < N) {
			
            // 검은 조약돌 개수를 넘었을 경우
            if (blackCnt > B) {
                if (road[start] == 'W') {
                    whiteCnt--;
                } else {
                    blackCnt--;
                }
				
                len--;
                start++;
            } else {
                if (road[end] == 'W') {
                    whiteCnt++;
                } else {
                    blackCnt++;
                }
				
                len++;
                end++;
            }
			
            // 조약돌 개수가 조건에 맞는 경우 최대값 갱신
            if (blackCnt <= B && whiteCnt >= W) {
                answer = Math.max(answer, len);
            }
        }
		
        System.out.println(answer);
    }
}