(백준) 점심메뉴 _ 12099

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

 

🐢 설명

lower bound, upper bound를 사용해서 풀면 되는 문제이다.

 

1. 주어진 음식 메뉴를 매운 순서로 정렬하고, 먹을 수 있는 범위인 u, v를 가지고 lower bound, upper bound를 구해준다.
2. 이 범위내에서 먹을 수 있는 달달한 메뉴를 찾아야 하므로 반복문을 통해 x, y 범위 비교해준다.
3. 2번에서 카운트한 개수가 곧 매운맛과 달달함이 충족된 메뉴의 개수이다.

총 Q번의 범위에 대해 N개의 메뉴들에 대해 이분탐색을 하고, 해당 범위 내에서 다시 탐색을 하게 된다. 따라서 대략 O(QN)의 시간 복잡도를 갖게 된다.

 

🐢코드

public class 점심메뉴_12099 {
    static int N;
    static int Q;
    static Menu[] menus;
    static StringBuilder answer = new StringBuilder();

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

        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        menus = new Menu[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int spicy = Integer.parseInt(st.nextToken());
            int sweet = Integer.parseInt(st.nextToken());
            menus[i] = new Menu(spicy, sweet);
        }

        Arrays.sort(menus, Comparator.comparing(m -> m.spicy));
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            findMenuCount(u, v, x, y);
        }
        System.out.print(answer);
    }

    private static void findMenuCount(int u, int v, int x, int y) {
        int[] bound = spicyMenuFind(u, v);
        int count = 0;

        for (int i = bound[0]; i < bound[1]; i++) {
            if (menus[i].sweet <= y && menus[i].sweet >= x) {
                count++;
            }
        }

        answer.append(count).append("\n");
    }

    private static int[] spicyMenuFind(int u, int v) {
        int start, end;
        int left = 0;
        int right = N;
        int mid;

        // lower bound
        while (left < right) {
            mid = (left + right) / 2;

            if (menus[mid].spicy < u)
                left = mid + 1;
            else
                right = mid;
        }
        start = right;

        left = start;
        right = N;
        // upper bound
        while (left < right) {
            mid = (left + right) / 2;

            if (menus[mid].spicy <= v)
                left = mid + 1;
            else
                right = mid;
        }
        end = right;

        return new int[]{start, end};
    }

    private static class Menu {
        int spicy;
        int sweet;

        public Menu(int spicy, int sweet) {
            this.spicy = spicy;
            this.sweet = sweet;
        }
    }
}

🐢 마무리