백준 1920번: 수 찾기[JAVA]

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

1920번: 수 찾기

[시간초과가 발생한 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        // ArrayList에 값을 담아줌
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            if (list.contains(Integer.parseInt(st.nextToken()))) { // list.contains() 함수를 사용
                bw.write("1");
            } else {
                bw.write("0");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

[정답코드]

import java.io.*;
import java.util.*;

public class Main {
    public static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        ArrayList<Integer> list = new ArrayList<>();
        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) {
                bw.write("1");
            } else {
                bw.write("0");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static int binarySearch(int key) {
        int low = 0; // 탐색 범위의 왼쪽 끝 인덱스
        int high = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스

        // low 가 high 보다 커지면 종료
        while (low <= high) {
            int mid = (low + high) / 2; // 찾는 범위의 중간 값

            if (key < arr[mid]) { // key 가 중간값보다 작을 경우
                high = mid - 1;
            } else if (key > arr[mid]) { // key 가 중간값보다 클 경우
                low = mid + 1;
            } else { // key 가 중간값과 같을 경우
                return mid;
            }
        }
        // 끝까지 탐색했지만 값이 존재하지 않을 경우
        return -1;
    }
}

 

[설명]

이 문제는 이분 탐색을 활용하면 풀 수 있는문제다. 하지만 처음에 봤을때 간단하게 보여서 list.contains() 메서드를 활용하면 풀릴것같아서 시도해보았다. 결과는 시간초과가 발생했다. 

contains 메서드의 설명을 보면 알 수 있듯이 contains 메서드도 결국에는 리스트의 처음부터 끝까지 탐색하기 때문에 내가 직접 반복문을 시행하나 메서드를 활용하나 별 차이가 없기 때문에 시간초과가 발생했다.

그래서 이분탐색을 활용해 다시 정답을 구해냈다. 코드는 간단해서 설명할것이 없을것 같고 나는 시간복잡도가 궁금해 자료를 검색해봤다.

이러한 일반적인 이분탐색은 거의 대다수가 O(logN) 의 시간 복잡도를 가진다.

N개의 요소를 가진 리스트를 K번 반복한다는 함수를 구한다면 다음과 같다.

운이 좋아 1번만에 찾는다면 (1/2)*N 가 될것이고 3번만에 찾는다면 (1/2)*(1/2)*(1/2)*N 이 될것이다.

운이 안좋아 최악의 경우로  마지막 탐색범위가 1인 경우가 있을수도있다. K번 반복 했을 때 쪼개진 크기가 1이라고 가정한다면, 결국  K번 반복한다고했으니 이를 다음과같이 풀어볼 수 있다.

결국 시간복잡도는 O(logN) 이 되는것이다.

원래 내가 작성했던 코드는 간단히 보자면 이중for문이 되는것이기 때문에 시간복잡도는 O(N^2) 혹은 O(NM)이 된다.