<이분 탐색> BOJ 14434 놀이기구 1

문제

문제 배경을 보면 모든 어린이의 첫날 키는 0이고 각 어린이마다 키가 1씩 크는 날이 길이 k의 배열로 주어집니다. 이런 상황에서 i 어린이와 j어린이가 키 제한이 있는 k놀이기구를 탈 수 있냐는 질문이 총 q개가 주어지고 정해진 기간동안 각 날짜마다 몇 개의 질문에 대해 그렇다를 답할 수 있는지 묻는 문제입니다.

접근

1. 모든 질문에 대해 날짜를 기준으로 이분 탐색을 하여 놀이기구 탑승이 가능한 첫번째 날을 찾는다.(키가 줄어들지는 않으니 탑승 가능한 첫번째 날부터는 마지막 날까지 탑승 가능하므로)

2. 특정 날짜에 두 아이가 해당 놀이기구를 탑승 가능한지 판단해야 한다.

   • 2-1. 키가 자라는 아이의 번호가 담긴 배열을 차례대로 하나하나 탐색한다.
     -> 시간 복잡도가 $O(q*logk*k)$가 되어 문제 제한에 맞는 풀이법이 아니다.
   • 2-2. 현재 날짜까지 배열을 잘라 정렬 후 upper_bound-lower_bownd로 해당 아이가 총 키가 몇번 자랐는지 카운트 해준다.
     -> 결국 정렬을 해주어야하므로 2-1보다 더 큰 시간 복잡도를 갖는다.
   • 2-3. 현재 날짜까지 해당 아이가 총 몇번 자랐는지만 알면 되기 때문에 q for문을 돌기 전에 미리 각 아이에 대해 키가 자라는 날짜를 저장해두고(길이 가변 배열 -> java의 경우 ArrayList 사용) 필요할 때마다 이분 탐색을 통해 현재 날짜까지 총 몇번 자랐는지 구해준다.
     시간 복잡도 $O(q*logk*logk)$로 사용 가능하다.

3. 길이 k의 answer배열을 미리 만들어두고(초기화 0) 각 질문마다 탑승 가능한 첫번째 날을 구해 answer[탑승 가능 첫번째 날] + 1을 해준다.
   모든 질문에 대한 탐색이 끝나고 남은 answer배열을 인덱스 1에서부터 마지막까지 순서대로 탐색하며 answer[i]에 answer[i-1]을 더해준다. 왜냐하면 i-1부터 탑승 가능하다고 답했던 질문은 i-1부터 마지막까지 탑승 가능하다고 답할 수 있으므로

4. answer 배열을 출력하면 정답

코드

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

class Main {
    static int n;
    static int m;
    static int k;
    static int q;

    static int[] limit;
    static ArrayList<Integer>[] list;

    static int find(int day, int child1) {
        int l = -1;
        int r = list[child1].size();

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

            if (list[child1].get(mid) <= day) {
                l = mid;
            } else {
                r = mid;
            }
        }

        return l + 1;
    }

    static boolean check(int day, int child1, int child2, int ride) {

        int height1 = find(day, child1);
        int height2 = find(day, child2);

        if (height1 + height2 >= limit[ride - 1]) {
            return true;
        }

        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");

        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        k = Integer.parseInt(temp[2]);
        q = Integer.parseInt(temp[3]);

        temp = br.readLine().split(" ");
        limit = new int[m];

        for (int i = 0; i < m; i++) {
            limit[i] = Integer.parseInt(temp[i]);
        }
        list = new ArrayList[n + 1];

        for (int i = 0; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }
        temp = br.readLine().split(" ");
        for (int i = 0; i < k; i++) {
            list[Integer.parseInt(temp[i])].add(i);
        }
        int[] answer = new int[k];

        for (int i = 0; i < q; i++) {
            temp = br.readLine().split(" ");
            int u = Integer.parseInt(temp[0]);
            int v = Integer.parseInt(temp[1]);
            int ride = Integer.parseInt(temp[2]);

            int l = -1;
            int r = k;

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

                if (check(mid, u, v, ride)) {
                    r = mid;
                } else {
                    l = mid;
                }
            }

            if (r == k)
                continue;
            answer[r] += 1;
        }

        for (int i = 1; i < k; i++) {
            answer[i] += answer[i - 1];
        }

        for (int i = 0; i < k; i++) {
            System.out.println(answer[i]);
        }

    }
}