백준 10816번 숫자 카드2

 

성능 요약

메모리: 165240 KB, 시간: 1616 ms

분류

이분 탐색, 자료 구조, 해시를 사용한 집합과 맵, 정렬

제출 일자

2024년 2월 10일 19:59:33

문제 설명

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

 

풀이 설명

시간제한은 1초고 카드의 개수는 각각 50만개씩 입력될 수 있기에 n^2으로 가게 되면 시간이 2.5초가 걸리게 된다.

따라서 최대 nlogn의 시간복잡도로 문제를 해결해야 한다.

 

퀵 솔트로 정렬을 해준 뒤 위에서 부터 차례대로 개수를 세어 Hash Map에 key 값으로 카드의 숫자를, 

value의 값으로 카드의 갯수를 넣어줬다.

 

이후 System.out을 써보았는데 무거운 메소드라 그런지 시간초과가 나서 BufferWriter를 통해 출력해주니 간단하게 통과했다.

 

 

public class Main{
    public static void main(String[] args)throws IOException{

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int a = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int x[] = new int[a];

        for(int i =0;i <a;i++){
            x[i] = Integer.parseInt(st.nextToken());
        }

        int b = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine());
        int x2[] = new int[b];

        for(int i =0;i <b;i++){
            x2[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(x);

        int cnt = 0;
        Map<Integer,Integer> k = new HashMap<Integer, Integer>();

        for(int i = 0 ;i<a;i++){
            if(i+1 < a && x[i] == x[i+1]){
                cnt++;
            }
            else if(i == a-1 && x[i] != x[i-1]){
                cnt = 1;
                k.put(x[i],cnt);
            }
            else{
                cnt++;
                k.put(x[i],cnt);
                cnt = 0;
            }
        }

        for(int i = 0;i<b;i++){
            if(k.get(x2[i]) == null){
                bw.write("0");
            }
            else {
                bw.write(String.valueOf(k.get(x2[i])));
            }
            bw.write(" ");
        }

        bw.flush();
    }
}