[Algorithm/Java] 백준 10816번 - 숫자 카드 2

---

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

---

📌 문제

문제 유형

• 자료 구조
• 이분 탐색
• 해시맵 활용

문제 설명

상근이는 숫자 카드 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보다 작거나 같다.

입출력 예시

입력

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

출력

3 0 0 1 2 0 0 2

🔍 문제 풀이

• 각 숫자에 대해 map.put(num, map.getOrDefault(num, 0) + 1)로 등장 횟수를 누적
• 이후 M개의 숫자에 대해 map.getOrDefault(key, 0)을 사용하여 카드의 보유 개수를 조회
• 조회된 개수는 StringBuilder를 통해 공백으로 이어 붙여 한 번에 출력
• 시간 복잡도는 O(N + M)으로 효율적임

HashMap

HashMap은 키(key)에 대한 값(value)을 저장하는 자료 구조로, 내부적으로 해시 함수를 사용해 빠르게 탐색이 가능하다.

주요 메서드:

메서드	설명
put(key, value)	키에 해당하는 값을 저장하거나 기존 값을 갱신
get(key)	키에 해당하는 값을 반환함
getOrDefault(key, default)	키가 존재하면 해당 값을, 존재하지 않으면 기본값을 반환
containsKey(key)	해당 키가 맵에 존재하는지 여부를 확인함

// 선언
Map<String, Integer> map = new HashMap<>();

// 값 추가 또는 갱신
map.put("apple", 3);
map.put("banana", 5);

// 값 조회
int a = map.get("apple");           // 3
int b = map.getOrDefault("pear", 0); // 키 없으면 기본값 0 반환

// 키 존재 여부 확인
if (map.containsKey("banana")) {
    System.out.println("바나나 있음!");
}

// 반복 순회
for (String key : map.keySet()) {
    System.out.println("key: " + key + ", value: " + map.get(key));
}

평균 시간 복잡도는 삽입/조회/삭제 모두 O(1) 로 매우 빠르다.

중복 키는 허용되지 않으며, 기존 키에 대해 put()을 하면 값이 덮어쓰기 된다.

getOrDefault는 꼭 써야 할까?

반복문에서 처음부터 값이 0으로 들어간다면, 굳이 getOrDefault(num, 0)을 써야 할까?

for (int i = 0; i < N; i++) {
    int num = Integer.parseInt(st.nextToken());
    map.put(num, map.getOrDefault(num, 0) + 1);
}

사용해야하는 이유

HashMap은 존재하지 않는 키를 조회할 경우 null을 반환한다.

따라서 아래처럼 단순히 get() 후 +1을 하면 NullPointerException이 발생한다.

map.put(num, map.get(num) + 1); //  null + 1 → 예외 발생

• getOrDefault(num, 0) 사용
  • 해당 key가 존재하면 → 그 value 반환
  • 해당 key가 존재하지 않으면 → 0 반환

💻 전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());
            sb.append(map.getOrDefault(key, 0)).append(" ");
        }

        System.out.println(sb);
    }
}

💭 배운 점

• HashMap을 사용해 중복된 정수의 개수를 효율적으로 세는 방법
• getOrDefault(key, default)를 사용하면 키가 존재하지 않을 때 기본값을 쉽게 설정할 수 있음

🔁 복습 템플릿

Map<Integer, Integer> map = new HashMap<>();

// 개수 세기
for (int num : arr) {
    map.put(num, map.getOrDefault(num, 0) + 1);
}

// 조회
int count = map.getOrDefault(target, 0);