[JAVA]숫자 카드 2(Baekjoon)

문제

문제

 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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

풀이

 처음에 한 생각은 배열에다 값을 할당하고, 우선 정렬을 한 다음 이진 탐색을 통하여 해당 값의 인덱스를 가져온다. 그리고, 그 인덱스를 전후로 동일한 값을 가지는 원소들을 탐색하는 식으로 알고리즘을 짰다.
그랬더니, 시간 초과가 발생하였다. 분석을 해보았다. 테스트 케이스의 경우는 아래와 같다.

1. 값이 배열의 처음부터 존재하는 경우
2. 값이 배열의 끝까지 존재하는 경우
3. 값이 배열의 중간에만 존재하는 경우

 인덱스의 처리를 어떻게 할까 고민하였다. 반복문을 통해 key값보다 크거나 작은 값을 가지는 원소에 도달하면 반복문 종료, 즉 key값을 가지는 원소들의 범위 하한값-1 부터 상한값+1까지 범위를 설정하게 된다. 또한, 1과 2의 경우를 설정해주어 인덱스가 배열의 크기나 -1을 가지면 반복문이 종료되어, 1의 경우에는 하한값이 -1로 설정되고, 2의 경우에는 상한값이 배열의 크기만큼 설정되어 Out of index가 발생하지 않도록 하였다.

 위의 방법에서 시작초과가 발생하여서, 구글링을 한 결과, 이 문제는 이진 탐색을 변형하여 푸는 응용 문제였다. 기존, 이진 탐색의 경우 정렬된 배열에서 중간값을 key값과 비교해 범위를 반으로 줄여나가며 탐색을 하는 메커니즘이다. 이 문제에서는 상계와 하계를 결정짓는데에 이진 탐색을 변형하여 사용한다. 코드는 아래와 같다.

    private static int lowerbound(int key){
        int lo = 0;
        int hi = arr.length;

        while(lo < hi){
            int mid = (lo + hi) / 2;
            //등호를 넣어 key값과 mid값이 동일하여도 상계를 줄여나감
            //최종적으로, key값보다 작은 값을 가지는 첫번째 index를 반환
            if(key <= arr[mid])
                hi = mid;

            else
                lo = mid + 1;
        }
        return lo;
    }

    private static int upperbound(int key){
        int lo = 0;
        int hi = arr.length;
        while(lo < hi){
            int mid = (lo + hi) / 2;
            //위와 반대로 key값과 mid값이 동일하면 하계를 키워나감
            //최종적으로, key값보다 큰 값을 가지는 첫번째 index를 반환
            if(key < arr[mid]){
                hi = mid;
            }
            else
                lo = mid + 1;
        }
        return lo;
    }

 이진 탐색을 상계, 하계를 찾는 두개의 탐색 메소드로 분리하여 상계, 하계를 찾고 이 범위에 속하는 원소의 개수를 출력한다.

public class _10816 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int[] arr;
    public static void main(String[] args) throws Exception{
        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(), " ");
        for(int i = 0; i < M; i++){
            int key = Integer.parseInt(st.nextToken());
            sb.append(upperbound(key) - lowerbound(key)).append(" ");
        }

        System.out.println(sb);
    }
}

결론

 이진 탐색으로 찾고, 그 반환값으로 다시 인덱스 전후를 탐색하는 과정을 거쳤기에 기존에 알고리즘은 시간 초과가 발생했다. 좀 더 창의적으로 생각할 수 있도록 하자. 알고있는 내용도 문제에 맞게 변형하여 효율적으로 설계할 수 있는 힘을 기르면 멋있는 개발자가 될 것이다.