백준 - 10816 - 숫자 카드2

Algorithm

백준 - 10816 - 숫자 카드2

YoonBing9 2021. 3. 29. 22:43

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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());
    }
}
 
Colored by Color Scripter

cs

알고리즘

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