백준 15831번 준표의 조약돌 (java)

[Gold IV] 준표의 조약돌 - 15831

문제 링크

성능 요약

메모리: 28852 KB, 시간: 256 ms

분류

두 포인터

제출 일자

2025년 4월 30일 09:46:20

문제 설명

그림1. 준표가 좋아하는 하얀색의 미미

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

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

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

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

입력

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

출력

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

 

풀이

시간복잡도를 생각해보면 이중포문을 통한 완전탐색은 불가능하다.

선형 또는 NlonN까지 가능하다.

 

WWBWWBW

같은 예제를 봤을 때, B의 인덱스는 해당 위치까지의 조약돌의 개수가 된다.

 

B의 인덱스와 그 다음 B의 인덱스의 차이는 그 사이에 있는 흰 조약돌의 개수라고 볼 수 있다.

 

이 아이디어를 기반으로 문제를 풀었다.

 

검정 조약돌의 인덱스만 담아둔 리스트를 하나 만들고

 

검정 조약돌의 개수가 제약사항과 같아질 때

 

 마지막 위치에 있는 검정 조약돌의 다음 위치에 있는 검정 조약돌의 인덱스 - 가장 첫 위치에 있는 검정 조약돌 이전의 인덱스

를 구해주면 전체 조약돌의 개수가 나온다.

 

가장 첫 위치나 가장 마지막 위치의 검정 조약돌 인덱스를 사용하지 않는 이유는 가장 첫 위치 검정 조약돌 이전에 있는 흰 조약돌의 개수도 체크를 해줘야 하기 때문이다.

 

여러 엣지 케이스를 처리해주면 문제를 풀 수 있다.

 

정석적인 풀이는 투 포인터를 이용해서 검정돌의 개수가 제한보다 커졌을 때 왼쪽 포인터를 앞으로 이동시키는 방식이라고 한다.

 

전체 코드

public class 구준표의조약돌 {
    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 bMax = Integer.parseInt(st.nextToken());
        int WMin = Integer.parseInt(st.nextToken());

        char[] load = new char[N];
        load = br.readLine().toCharArray();

        List<Integer> bIndex = new ArrayList<>();

        bIndex.add(-1);
        for(int i=0;i<N;i++) {
            if(load[i] == 'B'){
                bIndex.add(i);
            }
        }
        bIndex.add(N);

        if(bMax >= bIndex.size()-2){
            if(N - (bIndex.size()-2) >= WMin) {
                System.out.println(N);
                return;
            }
            System.out.println("0");
            return;
        }
        int max = 0;
        int flag = 0;
        int startIdx = 0;
        for(int i=1;i<bIndex.size()-1;i++) {
            if(i > bMax){
                flag = 1;
            }
            if(flag == 1){
                startIdx++;
            }
            if(i >= bMax && bIndex.get(i+1)-bIndex.get(startIdx)-bMax-1 >= WMin){
                max = Math.max(max,bIndex.get(i+1)-1-bIndex.get(startIdx));
            }
        }
        System.out.println(max);
    }
}