백준 10816. 숫자 카드 2

문제 링크

난이도	정답률(_%)
Silver 4	35.029%

설계

• 상근이가 가지고 있는 숫자 카드 개수 N, 최대 500,000

시간 복잡도

O(N)

공간 복잡도

최대 N개의 key를 가진 Map

풀이

• 상근이의 카드를 HashMap을 이용해 <카드 번호, 개수> 형태로 저장한다.
• Map에서 해당 카드 번호가 있으면 출력하고, 그렇지 않으면 0을 출력한다.

코드

• 나는 보자마자 Map을 떠올려서 풀었는데, 풀고나서 문제의 태그를 보니 이분탐색 문제였다. 시간이 되면 이분탐색으로도 한번 더 풀어볼 예정이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;

public class Main {
    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 cardsNumber = Integer.parseInt(br.readLine());
        Map<Integer, Integer> cards = new HashMap<>();
        String[] cardSet = br.readLine().split(" ");

        for (int i = 0; i < cardsNumber; i++) {
            int currentCard = Integer.parseInt(cardSet[i]);

            if (cards.get(currentCard) == null) {
                cards.put(currentCard, 1);
            } else {
                cards.put(currentCard, cards.get(currentCard) + 1);
            }
        }

        int chooseCardsNumber = Integer.parseInt(br.readLine());
        String[] chooseCardSet = br.readLine().split(" ");

        for (int i = 0; i < chooseCardsNumber; i++) {
            int cardNumber = Integer.parseInt(chooseCardSet[i]);

            if (cards.get(cardNumber) == null) {
                bw.write("0 ");
            } else {
                bw.write(Integer.toString(cards.get(cardNumber)) + " ");
            }
        }

        bw.flush();
        bw.close();
    }
}