[백준 JAVA] 10816 숫자 카드 2

10816 숫자 카드 2

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

 

문제설명

이진 탐색을 이용하여 숫자가 몇 개씩 있는지 계산

접근방식

O(M log N) 시간 복잡도

 

1. Arrays.sort()를 이용한 배열 정렬하는데 O(N log N)의 시간 소요

2. 이진 탐색하는데 O(log N)의 시간이 소요된다.

3. 각 숫자별로 M번만큼 이진 탐색을 하기 때문에 O(M log N)의 시간이 소요된다.

문제 조건 분석 과정

 

1. 배열에 숫자 개수 만큼의 정수를 담고, 정렬한다.

2. 배열 안에서 key 이상인 정수를 찾는다.

3. 각 숫자별로 상근이가 가지고 있는 숫자 카드 개수를 계산한다.

 

사용된 자료구조

• Arrays.sort(): 정수들을 배열에 담고 정렬하기 위해서 사용
• lowerBound, upperBound: 이진 탐색을 위한 반복문

전체코드

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

public class Main {

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

        // 숫자 카드의 개수 N 입력
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        // 숫자 카드에 적힌 정수들 입력 및 정렬
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        // 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 숫자의 개수 M 입력
        int M = Integer.parseInt(br.readLine());

        // 구해야 할 숫자들 입력
        st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        // 각 숫자에 대해 상근이가 가지고 있는 숫자 카드 개수 계산
        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());

            // 이진 탐색을 이용해 lowerBound와 upperBound의 차이를 구함
            sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
        }

        // 결과 출력
        System.out.println(sb);
    }

    // lowerBound 구하는 메서드
    private static int lowerBound(int[] arr, int key) {
        int n = 0;
        int m = arr.length;

        while (n < m) {
            int mid = (n + m) / 2;

            if (key <= arr[mid]) {
                m = mid;
            } else {
                n = mid + 1;
            }
        }

        return n;
    }

    // upperBound 구하는 메서드
    private static int upperBound(int[] arr, int key) {
        int n = 0;
        int m = arr.length;

        while (n < m) {
            int mid = (n + m) / 2;

            if (key < arr[mid]) {
                m = mid;
            } else {
                n = mid + 1;
            }
        }

        return n;
    }
}