[BackJoon]10815번

문제

 

숫자 카드는 정수 하나가 적혀 있는 카드이다. 

상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 

이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 

둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 

숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 

두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 

넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어 있다. 

이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

 

출력

 

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 

각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

풀이

 

정렬 없이 검색만 필요한 10만 개 단위의 자료에서 사용할 자료형은 역시 HashMap이다.

 

조금 딴소리지만 삽입도 빠르고 (여기선 필요 없지만) 중복도 알아서 제거해 주는 해시맵은 데이터의 수가 늘어날수록

 

효율이 떨어지는 재미있는 구조를 가지고 있다.

 

2022.12.17 - [Development/Technical Interview] - [면접 준비 - Java]Data Structures in a Nutshell

[면접 준비 - Java]Data Structures in a Nutshell

아무튼 상근이가 가진 카드를 해시맵에 넣어 앞으로 주어질 카드와 비교를 빠르게 하고,

 

스트링빌더를 하나 생성해 주어진 값이 셋에 존재할 경우 1을, 아닐 경우 0을 이어붙이도록 했다.

 

2023.01.18 - [Development/Technical Interview] - [면접 준비 - Java]String vs. String Buffer vs. String Builder

[면접 준비 - Java]String vs. String Buffer vs. String Builder

문제의 의도는 해시셋에 대해 조금 더 공부해 보고 사용하라는 것 같아서 지난 글을 다시 읽었다.

 

이외는 위에 쓰여진 것을 그대로 코드로 옮기고 끝.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Prob10815_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        int n = Integer.parseInt(br.readLine());
        Set<Integer> set = new HashSet<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            set.add(Integer.parseInt(st.nextToken()));
        }

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

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            if (set.contains(Integer.parseInt(st2.nextToken()))) {
                sb.append(1 + " ");
            } else {
                sb.append(0 + " ");
            }
        }

        System.out.println(sb);
    }
}