[백준-실버] 암기왕 (BOJ 2776)

문제

암기왕 링크

풀이

가장 먼저 생각났던 방식은 2중 반복문을 돌며 수첩 1에 적힌 값을 찾는 방식이었다. 하지만 시간 조건은 2초, N, M은 최대 1,000,000 개수를 갖을 수 있기에 다른 방법은 생각한 결과 Set, 이진 탐색 방법을 생각해냈다.

 

Set을 이용한 풀이

• 수첩1에 해당하는 값을 Set 자료구조에 저장
• 수첩2의 값을 입력받아서 Set에 존재하는지 확인하고 존재하면 1, 없으면 0을 bw에 작성
• T(테스트 케이스)가 모두 종료되면 버퍼에 저장되 문자열을 flush해서 내용을 출력한다.

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        for(int i = 0; i < T; i++) {
            int note1Length = Integer.parseInt(br.readLine());
            Set<Integer> set = new HashSet<>();
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < note1Length; j++) {
                set.add(Integer.parseInt(st.nextToken()));
            }

            int note2Length = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < note2Length; j++) {
                if(set.contains(Integer.parseInt(st.nextToken()))){
                    bw.write("1\n");
                }else {
                    bw.write("0\n");
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

이진 탐색을 이용한 풀이

• 이진 탐색에서 가장 중요한 것은 정렬이다.
• 수첩1에 해당하는 값을 입력받아 수첩1 배열에 저장한다.
• 수첩1을 오름차순으로 정렬한다.
• 수첩2에 해당하는 값을 입력받아 수첩 2 배열에 저장한다.
• 수첩 2를 반복문을 돌면서 해당 값이 수첩 1에 있는지 이진 탐색을 통해 조회후 있으면 1, 없으면 0을 버퍼에 저장한다.
• T(테스트 케이스)가 모두 종료되면 버퍼에 저장되 문자열을 flush해서 내용을 출력한다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        for(int i = 0; i < T; i++) {
            int note1Length = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] note1Arr = new int[note1Length];
            for(int j = 0; j < note1Length; j++) {
                note1Arr[j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(note1Arr);

            int note2Length = Integer.parseInt(br.readLine());
            int[] note2Arr = new int[note2Length];
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < note2Length; j++) {
                note2Arr[j] = Integer.parseInt(st.nextToken());
            }

            for(int note2: note2Arr) {
                int start = 0;
                int end = note1Length - 1;
                int mid = end / 2;

                boolean flag = false;
                while(start <= end) {
                    if(note1Arr[mid] > note2){
                        end = mid - 1;
                        mid = (start + end) / 2;
                    }else if(note1Arr[mid] < note2) {
                        start = mid + 1;
                        mid = (start + end) / 2;
                    }else {
                        flag = true;
                        break;
                    }
                }

                if(flag) {
                    bw.write("1\n");
                }else {
                    bw.write("0\n");
                }
            }

        }

        bw.flush();
        bw.close();
        br.close();
    }
}