[Baekjoon] 1920 수 찾기 - JAVA

 

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

 

---

✏️ 제출 답안

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

public class Main {
    static int[] arr;

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

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

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            if (binarySearch(Integer.parseInt(st.nextToken())) >= 0){
                sb.append(1).append("\n");
            } else sb.append(0).append("\n");
        }
        System.out.println(sb);
    }

    public static int binarySearch(int input) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == input) {
                return 0;
            } else if (input < arr[mid]) {
                high = mid - 1;
            } else  low = mid + 1;
        }
        return -1;
    }
}

 

BufferedReader, StringTokenizer, StringBuilder를 써서 최대한 시간을 단축하려고 했지만 그럼에도 처음에 시간초과가 났다. 배열 내에 특정 정수가 있는지 판단하는 코드로 InputStream을 사용했기 때문에 최적화 되지 않았던 것이었다. 이 문제는 이진 탐색을 써야했는데 아직 이진 탐색 알고리즘 코드가 익숙하지 않아서 검색을 통해서 해결했다. 

 

이진 탐색 알고리즘은 검색 범위를 줄여나가면서 검색 값을 찾는 알고리즘으로 정렬된 리스트에만 적용 가능하므로 Arrays.sort()를 적용해준 뒤 메서드를 사용해줬다.

 

이진 탐색 알고리즘

 

제출 현황