BOJ15831 준표의 조약돌(Java)

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

풀이 : 누적 합, 이분 탐색

사고 흐름

아이디어는 비교적 빠르게 떠올랐다. 우선 누적 합으로 색깔별 돌 누적 개수를 구한 후,

O(N LogN)으로 0부터 순차적으로 시작지점으로 해서 흰 돌을 최소치 이상 먹기 위한 최소 인덱스 wIdx와

검은 돌을 최대치 미만으로 먹기 위한 최대 인덱스 bIdx를 구한 후,

bIdx가 더 작은 경우 bIdx와 start의 거리 차이의 최댓값을 갱신해나갔다.

이를 위해 lower_bound를 따로 구현하였다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main
{
	static BufferedReader br;
	static StringBuilder sb;
	static StringTokenizer st;
	static int N, B, W;
	static int black[], white[];
	static int ans;
	static String str;
	
	public static int lower_bound(int[] arr, int key) {
		int left = 1, right = arr.length;
		
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (arr[mid] < key) {
				left = mid + 1;
			}
			else {
				right = mid;
			}
		}
		
		return left;
	}
		
	
	public static void solve() {
		for(int start = 1; start <= N; ++start) {
			int findB = black[start] + B + 1;
			if (str.charAt(start - 1) == 'B') {
				findB--;
			}
			
			int findW = white[start] + W;
			if (str.charAt(start - 1) == 'W') {
				findW--;
			}
			
			int bIdx = lower_bound(black, findB);
			int wIdx = lower_bound(white, findW);
			
			if (bIdx > 0 && wIdx > 0) {
				if (bIdx - 1 >= wIdx) {
					ans = Math.max(ans, bIdx - start);
				}
			}
		}
	}
	
	public static void main(String args[]) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		
		st = new StringTokenizer(br.readLine().trim());
		N = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		
		
		str = br.readLine().trim();
		
		black = new int [str.length() + 1];
		white = new int [str.length() + 1];
		
		for(int i = 1; i <= str.length(); ++i) {
			black[i] += black[i - 1] ;
			white[i] += white[i - 1];
			if (str.charAt(i - 1) == 'B') {
				black[i]++;
			}else {
				white[i]++;
			}	
		}
		
		solve();
		
		System.out.println(ans);
		                                                                            
	}
}

후기

풀고 보니 문제 태그에 투 포인터가 있었다. 거의 안 써본 방식이라 이 풀이로 다시 풀어봐야겠다.

Java로 넘어가면서 입출력, 자료구조, 라이브러리 함수 등에서 고난을 겪고 있다.

꾸준히 하다보면 금방 적응하겠지