[Baekjoon] 10816 숫자 카드 2 - JAVA

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1 복사

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1 복사

3 0 0 1 2 0 0 2

 

---

✏️ 제출 답안

 

✖️ 오답

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

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

        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());
        }

        int m = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st2.nextToken());
            int count = count(num, arr);
            sb.append(count).append(" ");
        }
        System.out.println(sb.toString());
    }

    private static int count(int num, int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (num == arr[i]) { count++; }
        }
        return count;
    }
}

 

⭕ 정답

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;

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

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());
            sb.append(upperBound(num)-lowerBound(num)).append(" ");
        }
        System.out.println(sb);
    }

    public static int lowerBound(int num) {
        int low = 0;
        int high = arr.length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (num <= arr[mid]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public static int upperBound(int num) {
        int low = 0;
        int high = arr.length;

        while (low < high) {
            int mid = (low + high) / 2;
            if (num < arr[mid]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

 

처음에 제출한 답은 효율이라고는 찾아볼 수 없게 단순하게 코드를 짰다. 역시나 시간초과.. 근데 BufferedBuilder랑 StringTokenizer, StringBuilder 를 사용해 내가 할 수 있는 최대한의 코드 최적화는 끝이었다. 문제는 알고리즘을 어떻게 짜느냐였는데 도저히 생각이 안나서 결국 구글리으로 이 문제에 사용할 알고리즘을 찾아보았다. 많은 사람들이 이 문제에 이진분류 알고리즘을 사용하였다.

 

🪄 이진 탐색 알고리즘

이진 탐색

 

이진 탐색 : 정렬된 리스트, 배열의 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법.

• 탐색 방법
  1. 배열 전체의 중간값을 target 값과 비교한다.
  2. 중간값이 target 값보다 크면 left~middle만, 작으면 middle~right만 선택한다.
  3. 선택한 부분에서 left, middle, right 값을 다시 설정하고 다시 target 값과 비교한다.
  4. target 값을 찾을 때까지 이를 반복한다.

• 시간 복잡도
  • 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2​N에 비례
  • 즉 탐색 범위를 절반씩 줄이며 시간복잡도는 O(logN​)을 보장

 

제출 현황