백준 10815번 - 숫자 카드 ( Java )

 

안녕하세요 besforyou 입니다

 

이번 그은 백준 10815번 - 숫자 카드 문제 풀이입니다.

 

 

---

문제 풀이

 

상근이가 가지고 있는 숫자 카드의 개수(N)와 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수의 크기가 매우 크므로 원하는 데이터를 빠르게 찾아낼 수 있는 자료구조가 필요합니다.

그래서 제가 선택한 자료구조는 HashSet입니다.

 

일반적인 배열이나 ArrayList의 contains() 메소드는 원하는 원소를 찾는데 걸리는 시간복잡도는 O(N)이지만 HashSet은 O(1)의 시간복잡도를 가져 원하는 데이터를 더 빠르게 찾을 수 있습니다. 다만, 원소를 정렬시키지 못하고 배열의 원소를 수정하기 어려운 단점이 있습니다.

 

 

---

 

풀이 과정 

 

1. N값을 입력받고 N개의 숫자카드 값을 HashSet에 저장한다.

 

2. M값을 입력받고 M개의 숫자를 입력받는다.

 

3. 입력받은 숫자가 HashSet에 존재하면 1, 존재하지 않으면 0을 출력한다.

 

 

---

 

코드

 

import java.io.*;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, M;
 
    public static void main(String [] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        N = Integer.parseInt(br.readLine());
 
        HashSet<Integer> numberSet = new HashSet<>();
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        for (int i = 0 ; i < N ; i++) {
            numberSet.add(Integer.parseInt(st.nextToken()));
        }
 
        M = Integer.parseInt(br.readLine());
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 0 ; i < M ; i++) {
            int check = Integer.parseInt(st.nextToken());
            if (numberSet.contains(check) == true) bw.write(1 + " ");
            else
                bw.write(0 + " ");
        }
 
        bw.write("\n");
        bw.close();
    }
}