[백준] 2776번 : 암기왕

2776번: 암기왕

---

[이분 탐색 or Set 이용]

카테고리가 이분 탐색으로 되어있지만, 이 문제는 Set을 이용해 값이 있는지 여부를 체크하는 것도 가능하다. Set은 값을 포함하는지에 대한 시간 복잡도가 O(1)이므로 굉장히 빠르다. 다른 컬렉션인 List의 contain()은 O(N)이다.

 

그래서 이분 탐색을 이용한 풀이와 Set을 이용한 풀이를 해보았다.

(+추가)

출력의 횟수가 최대 T * 1,000,000번 할 수 있으므로 System.out.println()을 이용한다면 메모리 혹은 시간 초과가 날 가능성이 높을 것 같아 StringBuilder를 이용하였다.

# Code </>

> 이분 탐색

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

public class Main {

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

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

        for(int a=0; a<t; a++){
            StringBuilder sb = new StringBuilder();
            int n = Integer.parseInt(br.readLine());
            int[] list = new int[n + 1];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++)
                list[i] = Integer.parseInt(st.nextToken());

            Arrays.sort(list);
            int m = Integer.parseInt(br.readLine());

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<m; i++){

                int left = 0, right = n, val = Integer.parseInt(st.nextToken());
                boolean find = false;

                while(left <= right){
                    int mid = (left + right) / 2;

                    if(list[mid] == val){
                        find = true;
                        break;
                    }
                    else if(list[mid] < val)
                        left = mid + 1;
                    else
                        right = mid - 1;
                }

                sb.append(find? 1 : 0).append("\n");
            }

            System.out.print(sb);
        }
    }
}

> Set 사용

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

public class Main {

    public static void main(String[] args) throws IOException {
        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);
        }
    }
}