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

안녕하세요 :)

적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.

혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자  글을 써 내려갑니다.

 

---

 

백준 10816 숫자 카드 2

이 문제는 N개의 숫자 카드 중 특정 숫자가 몇개 있는지 빠르게 세는 문제입니다.

처음에는 단순 반복문으로 비교하려다 시간초과가 발생했고, 이를 HashMap과 getOrDefault() 메서드로 해결한 풀이입니다.

 

📘 문제

 

💡 해결 방법

숫자의 개수를 빠르게 세야 하므로 Map을 사용합니다.

HashMap<Integer, Integer>에 숫자별 등장 횟수를 저장하고,

이후에 몇 개 있는지 확인해야 할 숫자 목록이 주어졌을 때 해당 숫자가 Map에 있으면 그 값을,

없으면 0을 출력합니다.

 

✅ 풀이 및 설명 (설명은 더보기 클릭)

 

• 처음에는 입력된 카드들을 배열에 담고, contains()나 이중 for문으로 비교를 시도했지만 시간 초과가 발생했습니다.
• 시간 복잡도를 줄이기 위해 Map 자료구조를 사용하여 각 숫자의 개수를 미리 저장해두고,
• 나중에 찾을 숫자는 Map.getOrDefault(숫자, 0)을 통해 빠르게 조회합니다.
  • countMap.put(num, countMap.getOrDefault(num, 0) + 1);
  • num이 이미 등장했으면 +1 해주고, 처음 보는 숫자면 0에서 시작해서 1로 넣어줍니다.
  • 처음 10 등장 → getOrDefault(10, 0) → 0 + 1 = 1 → countMap.put(10, 1)
  • 두 번째 10 등장 → getOrDefault(10, 1) → 1 + 1 = 2 → countMap.put(10, 2)
  • 세 번째 10 등장 → getOrDefault(10, 2) → 2 + 1 = 3 → countMap.put(10, 3)

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
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());
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 숫자 카드 배열 입력
        int[] arrN = new int[n];
        for (int i = 0; i < n; i++) {
            arrN[i] = Integer.parseInt(st.nextToken());
        }

        // 숫자와 등장 횟수를 저장할 HashMap 생성
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : arrN) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 체크할 카드 개수
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        // 결과를 저장할 StringBuilder
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int card = Integer.parseInt(st.nextToken());
            sb.append(countMap.getOrDefault(card, 0)).append(" ");
        }

        // 결과 출력
        System.out.print(sb);
        br.close();
    }
}

 

처음에는 단순한 비교로 풀 수 있을 거라고 생각했는데

N,  M이 최대 50만 개로 주어지기 때문에 이중 반복문으로는 시간 초과가 발생했습니다.

이를 해결하기 위해 HashMap을 사용해 등장 횟수를 저장하고,

getOrDefault()로 빠르게 조회하는 방법을 사용했더니 문제없이 통과할 수 있었습니다.

 

---

공부하면서 유용했던 부분 메모 겸 공유하고자 끄적입니다.

고쳐야 하는 부분 있다면 댓글 남겨주시면 수정하겠습니다.

행복한 하루 보내세요 (❁´◡`❁)