문제 출처

단계별로 풀어보기 > 집합과 맵 > 숫자 카드
https://www.acmicpc.net/problem/10815

문제 설명

상근이는 숫자 카드 N개를 가지고 있을 때, 정수 M개가 주어진다. 해당 정수들이 숫자 카드에 속하는 숫자인지 확인하여 가지고 있으면 1, 가지고 있지 않으면 0을 출력하라.

접근 방법

HashSet을 통해 빠르게 접근할 수 있다.
주어지는 숫자 카드를 HashSet에 저장하고, 주어지는 정수 M개를 contains메서드를 통해 확인한다.

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

public class 숫자_카드 {

    public static void main(String[] args) throws IOException {

        HashSet<Integer> cards = new HashSet<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for(int i = 0; i < N; i++){
            cards.add(Integer.parseInt(st.nextToken()));
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();


        for(int i = 0; i < M; i++){
            if(cards.contains(Integer.parseInt(st.nextToken()))) sb.append(1).append(" ");
            else sb.append(0).append(" ");
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }


}

알게된 점

HashSet을 이용하여 숫자 카드들의 수 N개를 저장하고, 정수 M개 만큼 반복하면 시간 복잡도 O(N + M) 안에 해결할 수 있다.

문제푼 흔적