백준 28140 (빨강~ 빨강~ 파랑! 파랑! 달콤한 솜사탕!) - java

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

 

문제

알파벳 대문자로 이루어진 길이 N의 문자열 S=S0S1S2⋯SN−1가 주어진다.

구간 [l,r]$[l, r]$이 주어질 때, 아래의 규칙을 만족하는 정수 a, b, c, d를 찾으면 당신은 달콤한 솜사탕을 얻을 수 있다.

•  Sa=Sb= R
•  Sc=Sd=B
•  l≤a<b<c<d≤r

구간이 Q번 주어질 때 달콤한 솜사탕을 얻을 수 있으면 그때의 a, b, c, d를 아무거나 하나 출력하고, 얻을 수 없으면 -1을 출력한다.

 

유형 : 이진탐색

 

접근 방식

• R R B B 순으로 찾아야 한다. 사용자는 l,r 값을 입력한다.
• R배열에서 lower_bound로 l값을 찾는다.
  • 여기서 첫번째 값과 두번째 값을 추출한다.
• B배열에서 lower_bound로 위에서 구한 두번째 R값을 바탕으로 값을 찾는다.
  • 해당 값의 첫번째 값과 두번째 값을 찾는다.

 

코드

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

public class BOJ_28140_달콤한_솜사탕 {

    static int n,m;
    static char[] arr;
    static ArrayList<Integer> rList = new ArrayList<>();
    static ArrayList<Integer> bList = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n  = Integer.parseInt(st.nextToken());
        m  = Integer.parseInt(st.nextToken());

        arr = br.readLine().toCharArray();

        for(int i = 0 ; i < n ; i++) {
            if(arr[i] == 'R') {
                rList.add(i);
            }else if(arr[i] == 'B') {
                bList.add(i);
            }
        }

        StringBuilder sb = new StringBuilder();

        int[] result = new int[4];

        for(int i = 1 ; i <= m ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            int rIdx = lower(rList,l);

            if(rIdx + 1 >= rList.size() || rList.get(rIdx + 1) > r) {
                sb.append("-1\n");
                continue;
            }

            result[0] = rList.get(rIdx);
            result[1] = rList.get(rIdx + 1);

            int bIdx = lower(bList, result[1]);

            if(bIdx + 1 >= bList.size() || bList.get(bIdx + 1) > r) {
                sb.append("-1\n");
                continue;
            }

            result[2] = bList.get(bIdx);
            result[3] = bList.get(bIdx + 1);

            sb.append(result[0]+" "+result[1]+" "+result[2]+" "+result[3]+"\n");
        }

        System.out.print(sb);
        br.close();
    }

    static int lower(ArrayList<Integer> list, int target) {
        int l = 0;
        int r = list.size();

        while(l < r) {
            int mid = (l + r) / 2;

            if(list.get(mid) < target) {
                l = mid + 1;
            }else {
                r = mid;
            }
        }

        return l;
    }
}