[백준] 10815번 : 숫자 카드 - 자바(JAVA)

문제 해석

int형 범위내의 N개의 숫자가 주어집니다.

이때 M개의 숫자가 다시 주어지고 M개의 숫자가 N개의 숫자에 존재하는지 탐색하는 문제입니다.

 

문제 풀이 전 설계

N제한이 50만이기 때문에 O(N^2)은 불가능합니다.

또한 문제에서는 정렬/이분 탐색으로 문제를 해결하라고 제시했지만 더 효율적인 방법인 HashSet을 이용하면 O(1)의 시간복잡도로 해결이 가능할 것 같습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_10815_숫자카드 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        //숫자를 담아둘 집합 Set 선언
        Set<Integer> numbers = new HashSet<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            numbers.add(Integer.parseInt(st.nextToken()));
        }
        //숫자 입력 끝

        //true = 1 / false = 0인 결과를 담을 리스트
        List<Integer> result = new ArrayList<>();

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++){
            int curNum = Integer.parseInt(st.nextToken());
            //집합에 curNum이 포함되어있는지 검사
            if(numbers.contains(curNum)){
                //포함되어있으면 리스트에 true : 1 추가
                result.add(1);
                continue;
            }
            //포함되어있지 않으면 리스트에 false : 0 추가
            result.add(0);
        }

        //result 리스트를 순회하면서 StringBuilder에 1 또는 0으로 쌓여있는 결과 출력을 위한 과정
        StringBuilder sb = new StringBuilder();
        for(Integer cur : result){
            sb.append(cur+ " ");
        }

        System.out.println(sb.toString());

    }
}