[JAVA / 자바] 백준 10816 - 숫자 카드 2

문제

숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

---

 

---

문제 접근 방법

이번 문제는 카운팅 정렬(counting sort, 계수 정렬)로 쉽게 풀 수 있는 문제이다.

숫자의 범위는 -10,000,000부터 10,000,000까지 이므로 카운팅 정렬을 사용하려면 배열의 크기를 최소 20,000,001개를 잡아야 한다. 이때, 배열의 인덱스에는 음수는 존재하지 않으므로 각 숫자당 인덱스의 위치는 숫자+10,000,000이다. 따라서 숫자 입력이 들어오면 각 숫자의 해당하는 인덱스의 +1을 해주고, 후에 숫자 카드의 개수를 찾을 땐 마찬가지로 해당 수의 인덱스에 저장되어있는 값을 출력하기만 하면 되는 간단한 문제이다.

---

JAVA 코드 풀이

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

public class Main {
    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());
        StringTokenizer cardToken = new StringTokenizer(br.readLine());
        int card[] = new int[20000001];
        for(int i=0; i<n; i++)
            card[Integer.parseInt(cardToken.nextToken())+10000000] += 1;
        int m = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++)
            bw.write(card[Integer.parseInt(st.nextToken())+10000000]+" ");
        bw.close();
    }
}

코드 실행 결과

---

후기

카운팅 정렬은 메모리 낭비가 매우 심하다 안 쓰는 숫자까지 배열을 잡아놓아야 하기 때문이다.  그렇지만 해당 숫자 카드의 개수를 출력할 때나 개수를 추가할 때 탐색을 하지 않아도 되고, 구현이 매우 쉽다는 장점이 있다. 따라서 상황에 따라 어떤 방법으로 구현할 것인지 판단하여 유동적으로 사용하면 될 것 같다.

 

---

문제 원본

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