[10816] 숫자 카드 2

난이도: ★★☆☆☆ • solved on: 2025-12-31

---

문제 요약

• 문제 유형: 해시맵(HashMap), 카운팅(counting)
• 요구사항: N개의 정수 카드에서 각 질의 수가 몇 개 있는지 개수를 출력해야 한다.

---

사용 개념

1. 자료구조

   • HashMap<Integer, Integer>: (숫자 → 등장 횟수) 저장

2. 알고리즘/기법

   • 빈도수 카운팅 (frequency counting)
   • getOrDefault를 이용한 안전 조회

3. 핵심 키워드

   • 평균 O(1) 조회
   • 중복 원소 개수(count)

---

풀이 아이디어 및 코드

방법 1 : HashMap을 활용한 누적 카운팅

1. 문제 분해

• N개의 카드를 읽으면서 map에 숫자별 등장 횟수를 누적한다.
• M개의 질의를 읽으면서 map.getOrDefault(q, 0)으로 개수를 출력한다.

2. 핵심 로직 흐름

   입력 N
   카드 N개를 map에 카운팅
   
   입력 M
   질의 M개에 대해 map[q] 출력 (없으면 0)

3. 예외 처리

   • 질의 숫자가 없는 경우 0 출력 (getOrDefault)

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        HashMap<Integer, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        String m = br.readLine();
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        while(st.hasMoreTokens()){
            int temp = Integer.parseInt(st.nextToken());
            map.put(temp, map.getOrDefault(temp, 0) + 1);
        }

        while(st2.hasMoreTokens()){
            int q = Integer.parseInt(st2.nextToken());
            sb.append(map.getOrDefault(q, 0)).append(" ");
        }

        System.out.println(sb);
    }
}

---

방법 2 : 정렬 + 이분 탐색

1. 개선 포인트

• 해시맵 풀이도 정답이고 빠르지만, 이 문제는 전형적으로 정렬 후 lower/upper bound로 개수를 세는 풀이도 자주 사용한다.
• 해시맵은 평균 O(1)이지만, 정렬 기반 풀이는 성능이 안정적이고(결정적), 구현 연습 가치가 있다.

2. 핵심 로직 흐름

   카드 배열 정렬
   count(x) = upperBound(x) - lowerBound(x)

3. 예외 처리

   • 카드에 없는 값이면 두 bound가 같아 0

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

public class Main {
    static int lowerBound(int[] arr, int target) {
        int l = 0, r = arr.length; // [l, r)
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (arr[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    static int upperBound(int[] arr, int target) {
        int l = 0, r = arr.length; // [l, r)
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (arr[mid] > target) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) cards[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(cards);

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int q = Integer.parseInt(st.nextToken());
            int cnt = upperBound(cards, q) - lowerBound(cards, q);
            sb.append(cnt).append(' ');
        }
        System.out.print(sb);
    }
}

---

시간·공간 복잡도

방법 1 (HashMap)

• 시간 복잡도: O(N + M) (평균)
• 공간 복잡도: O(N) (서로 다른 값 개수만큼)

방법 2 (정렬 + 이분 탐색)

• 시간 복잡도: O(N log N + M log N)
• 공간 복잡도: O(N)

---

어려웠던 점

• 없음

---

배운 점 및 팁

• 이 문제는 카운팅이므로 해시맵이 가장 직관적이다.

• 코딩 테스트 관점에서는

  • 빠르게 맞추기: 해시맵
  • 기본기/안정성 연습: 정렬 + lower/upper bound
    둘 다 정석 범위에 들어간다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/10816
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 10815번 숫자 카드
  • 백준 - 14425번 문자열 집합

• 확장 문제 (GPT 추천):

  • 백준 - 1764번 듣보잡
  • HackerRank - Frequency Queries