백준 - 10816 - 숫자 카드2

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
 
public class 숫자_카드_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.nextLine();
        String[] cards = sc.nextLine().split(" ");
        sc.nextLine();
        String[] numbers = sc.nextLine().split(" ");
        Map<String, Integer> map = new HashMap<>();
 
        for(int i=0; i<cards.length; i++) {
            map.put(cards[i], map.get(cards[i]) == null ? 1 : map.get(cards[i]) + 1);
        }
 
        StringBuilder result = new StringBuilder();
        for(int i=0; i<numbers.length; i++) {
            result.append((map.get(numbers[i]) == null ? 0 : map.get(numbers[i])) + " ");
        }
 
        System.out.println(result.toString().trim());
    }
}
 

알고리즘

• 해싱
• 해싱을 이용해 O(n^2)을 O(n)으로 풀어야 하는 문제.
• 해쉬맵을 이용하여 카드의 갯수를 저장하고 숫자에 맞는 카드수를 해쉬맵에서 가져오면 된다.