백준 10816 숫자 카드 2

문제

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

코드

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

public class Main {
    public static int count(int[] array, int n, int[] counting) {
        int index = Arrays.binarySearch(array, n);
        if (index >= 0)
            return counting[array[index]+10000000];
        else
            return 0;
    }

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

        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int[] nArray = new int[n];
        for (int i = 0; i < n; i++)
            nArray[i] = Integer.parseInt(st.nextToken());
        int[] counting = new int[20000001];
        for (int i = 0; i < nArray.length; i++)
            counting[nArray[i] + 10000000]++;

        int[] ans = counting.clone();

        for (int i = 0; i < counting.length - 1; i++)
            counting[i + 1] += counting[i];

        int[] sortedN = new int[n];
        for (int i = nArray.length - 1; i >= 0; i--) {
            sortedN[--counting[nArray[i] + 10000000]] = nArray[i];
        }

        int m = Integer.parseInt(br.readLine());
        s = br.readLine();
        st = new StringTokenizer(s);
        int[] mArray = new int[m];
        for (int i = 0; i < m; i++) {
            mArray[i] = Integer.parseInt(st.nextToken());
            bw.write(count(sortedN, mArray[i], ans) + " ");
        }
        bw.flush();
    }
}

해결 과정

1. 단순히 M개의 정수가 N 배열 안에 몇 개 있는지 찾으면 되는 문제이다. N 배열을 자바의 sort를 사용해서 오름차순으로 정렬해두고, M 배열의 인덱스 0부터 끝까지 Binary Search로 N 배열에서 탐색했다. 그 후 동일한 값이 더 있는지 보기 위해서 N 배열의 해당 인덱스에서 바로 앞의 값이 동일한 값이 아닐 때까지 이동한 후 같은 숫자가 나오는 개수를 카운팅 해서 리턴 했다.
2. 시간 초과(M 배열에서 같은 원소의 경우 매번 탐색해야 해서 시간이 오래 걸린다)
3. M 배열을 2차원 배열로 만들어서 [0]에는 값, [1]에는 탐색한 결과를 저장한 뒤 M 배열의 인덱스 1부터 탐색할 때 현재의 인덱스보다 앞선 M 배열의 인덱스에서 값이 같다면 새로 탐색하지 않고 그 인덱스의 [1] 값을 바로 출력해줬다. (M 배열도 같은 값이 있는 지 Binary Search 시도했지만 구현 실패해서 인덱스 0 -> 현재의 인덱스 -1 까지 Linear Search 구현)
4. 시간 초과(자바에서 제공되는 Arrays.sort()가 시간이 오래 걸린다, 3번의 방법도 효과가 없었던 것 같다)
5. N 배열을 오름차순 정렬할 때 Arrays.sort()를 사용하지 않고 Counting Sort 알고리즘 구현. N 배열에 들어갈 수 있는 수의 범위가 -10000000<=X<=10000000 이기 때문에 counting 배열의 인덱스를 0부터 맞춰주기 위해 nArray[i]+10000000을 counting 배열의 인덱스로 사용했다.
   
   3번에서 했던 수정은 없애고 원래대로 M 배열의 인덱스 0부터 끝까지 탐색했다.(최종적으로 N 배열의 정렬 알고리즘만 O(n)으로 수정)
6. 😁