[JAVA]백준 - 1920.수 찾기

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

풀이 > 

이중 for문으로 단순 검사를 해서 제출했더니 시간초과가 나왔다...!
검색해보니 이분탐색을 해야한대서 적용해보았다
자바에서 제공하는 Arrays.binarySearch 메소드가 있어서 쉽게 구현이가능했다

Arrays.binarySearch :
이분탐색을 진행해 첫번째 인수인 배열(a)에 두번째인수 값(stM.naxtToken())이 존재한다면
해당 인덱스를 반환한다.
존재하지 않는 값이면 음수로 인덱스를 반환하기때문에 
if ( index>0 ) 구문을 통해 양수 인덱스가 반환된다면 값이 존재한다고 판단해 1을 출력 

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

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

        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        StringTokenizer stN = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(stN.nextToken());
        }
        // 이분탐색을 하기위해 오름차순으로 정렬하기
        Arrays.sort(a);

        int m = Integer.parseInt(br.readLine());
        StringTokenizer stM = new StringTokenizer(br.readLine());

        for (int i = 0; i < m; i++) {
            // 이분 탐색
            int index = Arrays.binarySearch(a, Integer.parseInt(stM.nextToken()));
            if (index < 0) bw.append(String.valueOf(0));
            else bw.append(String.valueOf(1));
            bw.append("\n");
        }

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

 

다른 풀이 > 

이분탐색 메소드를 직접 구현하기

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

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

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

        int m = Integer.parseInt(br.readLine());
        StringTokenizer stM = new StringTokenizer(br.readLine());

        for (int i = 0; i < m; i++) {

            if (binarySearch(a, Integer.parseInt(stM.nextToken())) == -1) bw.append(String.valueOf(0));
            else bw.append(String.valueOf(1));
            bw.append("\n");
        }

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

    // 이분 탐색
    public static int binarySearch(int[] array, int num) {
        int start = 0;
        int end = array.length - 1;

        int mid;
        while (start <= end) {
            mid = (start + end) / 2;
            if (array[mid] == num) {
                return array[mid];
            } else if (array[mid] > num) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
}