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

2025-07-04 6 분 소요

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

🔍 문제 풀이

방법1. HashMap

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

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

주요 메서드:

메서드	설명
`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 반환

방법2. 이분 탐색

이분 탐색을 사용하여, 숫자 카드를 정렬한 뒤, 각 쿼리마다 lowerBound, upperBound로 특정 수가 몇 번 등장하는지 계산할 수 있음

함수	의미	설명
`lowerBound(arr, target)`	target 이상 이 처음 나오는 위치	`arr[mid] >= target`이면 왼쪽 탐색
`upperBound(arr, target)`	target 초과 가 처음 나오는 위치	`arr[mid] <= target`이면 오른쪽 탐색

두 위치의 차가 곧 등장 횟수
시간 복잡도: O(N log N + M log N)

예시

arr = {1, 2, 2, 2, 3, 4}, target = 2

lowerBound → index 1 (처음 2 등장)
upperBound → index 4 (3 등장 위치)
→ 등장 횟수 = 4 - 1 = 3

배열: [1, 3, 5, 7, 9], 찾을 값: x = 5
초기 상태: low = 0, high = 5 (배열 길이)

low	high	mid	nums[mid]	비교	조정
0	5	2	5	5 ≥ 5	high = mid = 2
0	2	1	3	3 < 5	low = mid+1 = 2
2	2				종료 조건 충족

구현 코드

입력 받은 숫자 카드 배열을 정렬
각 쿼리 target에 대해 lowerBound와 upperBound를 호출해 개수 계산
upper - lower가 곧 target의 등장 횟수

💡 x > nums[mid]이면 정답이 무조건 오른쪽에 있으니 mid를 버리고, 아니면 정답이 무조건 왼쪽에 있는데 mid가 정답일 수 있어 mid를 포함시켜 탐색시키는 것

// target 이상 첫 위치
public static int lowerBound(int[] arr, int target) {
    int low = 0, high = arr.length;
    while (low < high) {
        int mid = (low + high) / 2;
        if (arr[mid] < target) low = mid + 1;
        else high = mid;
    }
    return low;
}

// target 초과 첫 위치
public static int upperBound(int[] arr, int target) {
    int low = 0, high = arr.length;
    while (low < high) {
        int mid = (low + high) / 2;
        if (arr[mid] <= target) low = mid + 1;
        else high = mid;
    }
    return low;
}

왜 바로 return 하지 않을까?

arr[mid] == target일 때 바로 return 하면 처음 등장하는 위치를 놓칠 수 있다.

예를 들어,

arr = {1, 2, 2, 2, 3, 4};
target = 2;

mid가 2나 3이라면 arr[mid] == 2이지만, 처음으로 2가 나오는 위치는 = index 1
즉, arr[mid] == target이라고 해서 바로 return하면 오답이 나올 수 있다.
따라서,
- arr[mid] == target일 때에도 정답일 가능성은 있으니 버리지는 않고
- 왼쪽에도 같은 값이 있을 수 있으니 high = mid로 mid를 포함시킨 후,
- 범위를 계속 줄여 나가며 가장 왼쪽의 위치를 찾는다.

while (low < high)를 쓰는 이유

lowerBound, upperBound는 정확한 “시작 위치”를 찾는 이진 탐색이기 때문에 while (low < high)를 사용해야 안전하다.

werBound(x) → x 이상이 처음 나오는 위치
upperBound(x) → x 초과가 처음 나오는 위치

이럴 때는 low와 high가 딱 붙으면 루프를 종료해야 하는데,
그래서 low == high가 되는 순간 바로 탈출하도록 low < high로 설정하는 것이다.

만약 low <= high를 쓰면?

마지막 비교에서 low == high일 때도 mid를 한 번 더 비교하게 되고, 인덱스를 한 칸 넘겨버릴 수도 있어 인덱스 위치가 어긋날 수 있다.

정확한 값의 위치를 찾는 일반적인 이진 탐색(예: x == arr[mid]을 검사하는 경우)에
while (low <= high)를 사용한다. (탐색 종료 후 low > high가 되기 때문)

💻 전체 코드

HashMap

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));

        int n = Integer.parseInt(br.readLine());
        Map<Integer, Integer> map = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            int target = Integer.parseInt(st.nextToken());
            map.put(target, map.getOrDefault(target, 0) + 1);
        }
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<m; i++){
            int key = Integer.parseInt(st.nextToken());
            int result = map.getOrDefault(key, 0);
            sb.append(result).append(" ");
        }
        System.out.println(sb);

    }
}

이분 탐색

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());
        int[] nums = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums); // 이분 탐색을 위한 정렬

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++){
            int target = Integer.parseInt(st.nextToken());
            int lower = lowerBound(nums, target);
            int upper = upperBound(nums, target);
            sb.append(upper - lower).append(" ");
        }

        System.out.println(sb);
    }

    // target 이상이 처음 나오는 위치
    public static int lowerBound(int[] arr, int target) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    // target 초과가 처음 나오는 위치
    public static int upperBound(int[] arr, int target) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

💭 배운 점

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

또한, 이분 탐색을 활용하여 정렬된 배열에서 특정 수의 개수를 upperBound - lowerBound로 구할 수 있다는 것을 알게 됨
arr[mid] == target이어도 바로 리턴하지 않고 범위를 좁혀가는 이유가 헷갈렸는데, 완전히 이해하게 됨
그 이유는, 처음 등장 위치를 놓치지 않기 위해서임

박시은