문제 출처

단계별로 풀어보기 > 집합과 맵 > 숫자 카드 2

문제 설명

상근이가 가진 숫자 카드 N개가 주어지고, 정수 M개가 주어질 때, 상근이가 가진 숫자 카드 중에서 정수 M개의 숫자 각각은 몇개가 있는지 각 숫자마다 출력하라.

접근 방법

HashMap을 통해 상근이가 가진 숫자 N개를 저장한다. 이 때, value로 숫자 카드 갯수를 저장한다.(getOrDefault 메서드 이용)
이 후, 주어지는 숫자 M개를 get을 통해 StringBuilder에 append 하여 출력한다.

import java.io.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

public class 숫자_카드_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        HashMap<Integer, Integer> cards = new HashMap<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int M = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();

        for(int j = 0; j < M; j++){
            int k = Integer.parseInt(st.nextToken());

            if(cards.get(k) != null) sb.append(cards.get(k)).append(" ");
            else sb.append(0).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

해당 문제의 시간 복잡도는 O(N+M)이다. 이유는 HashMap의 put, get, getOrDefault 메서드들은 시간 복잡도 O(1)을 가지고, 각각의 반복문 N개, M개를 반복하기 때문이다.

문제푼 흔적