[백준] 1920번 수 찾기 (JAVA)

문제

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

설명

N개의 정수가 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내야 한다.

매번 하나씩 숫자를 비교하면서 탐색할 수 있지만 시간복잡도를 줄이기 위해 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 이분 탐색을 수행한다. 이분 탐색을 하기 위해서는 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있기 때문에 먼저 입력받은 수를 오름차순으로 정렬한다.

int[] nums = new int[N];

StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
    nums[i] = Integer.parseInt(st.nextToken());
}

Arrays.sort(nums);

이분 탐색은 시작점과 종료점을 이용해 중간점을 구해 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정이다. 계속 해당 과정을 하다가 시작점과 종료점이 역전되는 경우 현재 배열에 찾는 데이터가 없다는 의미이므로 종료한다.

void find(int num, int start, int end) {
    // start과 end가 역전되면 존재하지 않는다는 의미이다
    if (start > end) {
        System.out.println("0");
        return;
    }

    // mid를 구해서 이분 탐색을 수행한다
    int mid = (start + end) / 2;
    if (nums[mid] == num) {
        System.out.println("1");
    }
    else if (num < nums[mid]) {
        find(num, start, mid - 1);
    }
    else {
        find(num, mid + 1, end);
    }
}


for (int i = 0; i < M; i++) {
    int num = Integer.parseInt(st.nextToken());
    find(num, 0, N - 1);
}

 

전체 코드

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

public class Main {
    static int N, M;
    static int[] nums;

    static void find(int num, int start, int end) {
        // start과 end가 역전되면 존재하지 않는다는 의미이다
        if (start > end) {
            System.out.println("0");
            return;
        }

        // mid를 구해서 이분 탐색을 수행한다
        int mid = (start + end) / 2;
        if (nums[mid] == num) {
            System.out.println("1");
        }
        else if (num < nums[mid]) {
            find(num, start, mid - 1);
        }
        else {
            find(num, mid + 1, end);
        }
    }

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

        N = Integer.parseInt(br.readLine());

        nums = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);

        M = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            find(num, 0, N - 1);
        }
    }
}