BOJ 2776 - 암기왕

문제

수첩 1에 적힌 수 중에서 수첩 2의 각 수가 존재하는지 판별하라.

입력

테스트 케이스 수 T, 각각 수첩 1의 수 N개, 수첩 2의 수 M개가 주어진다.

출력

수첩 2의 각 수에 대해 수첩 1에 있으면 1, 없으면 0을 출력한다.

예제

입력	출력
`1` `5` `4 1 5 2 3` `5` `1 3 7 9 5`	`1` `1` `0` `0` `1`

풀이

HashSet에 수첩 1의 수를 저장한 뒤, 수첩 2의 각 수를 O(1)에 조회한다.

수첩 1의 N개 수를 HashSet에 넣는다
수첩 2의 각 수에 대해 set.contains()로 존재 여부를 판별한다
결과를 StringBuilder로 모아 출력한다

핵심 아이디어: 이분 탐색 대신 HashSet을 사용하여 조회를 O(1)로 최적화한다. 정렬이 필요 없어 더 간결하다.

코드

package day449;
 
import java.io.*;
import java.util.*;
 
public class Day400BOJ2776암기왕 {
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    int t = Integer.parseInt(br.readLine());
 
    for (int a = 0; a < t; a++) {
      Set<Integer> set = new HashSet<>();
      StringBuilder sb = new StringBuilder();
      int n = Integer.parseInt(br.readLine());
 
      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());
 
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < m; i++)
        sb.append(set.contains(Integer.parseInt(st.nextToken())) ? 1 : 0).append("\n");
 
      System.out.print(sb);
    }
  }
}

복잡도

시간: O(N + M) - HashSet 삽입 O(N) + 조회 O(M)
공간: O(N) - HashSet

문제