[BOJ 2230] 수 고르기 - JAVA, Gold5

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

2230번: 수 고르기

풀이

사용한 알고리즘: Binary Search

 

풀이전략

 

이분탐색을 통해 특정 값과 오차가 M 이상이면서 가장 적은 오차의 수를 구하면 된다.

 

완전 탐색을 통해 값을 비교하게 되면 시간 복잡도가 O(n^2)으로

n이 최대 100,000 까지 가능하다 했기 때문에 최대 10,000,000,000번(10억 번)의 연산을 하게된다.

 

그런데 JAVA는 통상 1초당 1억번의 연산을 수행한다.

따라서 제한시간이 2초가 주어진 상황에서 10억번의 연산을 하게되면 시간초과가 발생한다.

 

반면 이분 탐색의 시간 복잡도는 O(nlogn)으로 최악의 경우,

100,000 * log100,000 = 100,000 * 16.609640474437 = 약 1,660,664가 된다.

JAVA로 연산하는데 약 0.016초가 소요되는 것을 알 수 있다.

 

코드에서는 전형적인 이분 탐색 알고리즘이 사용됐다.

배열에서 비교할 시작 인덱스 지점인 start와 끝점인 end를 두고, 

두 값의 중간 값 인덱스를 가진 배열의 값과

우리가 비교하고 싶은 값을 비교하여 우리가 구하는 최적의 값을 보다 효율적으로 찾아낸다.

 

다만 이 문제에서 주의할 점은

start의 시작 인덱스값을 우리가 찾을 값의 배열 내 인덱스 값으로 정의해줘야 하는 것이다.

 

왜 start의 시작 인덱스 값을 0이 아닌 비교할 값의 인덱스 값으로 정의해줘야 하는지 알아보자.

 

만약 문제에서 입력으로

8 3
1
3
5
7
9
11
13
15

가 주어졌다고 가정해보자.

 

그런데 start를 항상 0으로 두고 비교를 하게되면 아래와 같은 문제가 발생한다.

target이 mid보다 큰 상황이면서 A[target]-A[mid] > M 이면

target은 보다 뒤에 있는 값들과 비교를 할 수 없고 자기보다 작은 인덱스의 값들과만 비교가 가능하다.

 

그런데 해당 비교는 target을 비교하기 전 0~4 번 인덱스를 먼저 비교해보며 이미 비교했던 내용들이다.

 

따라서 전혀 의미가 없으며, target 뒤의 값들과 비교를 할 수 없어지기 때문에

정확한 답을 도출해낼 수 없다.

 

따라서 start의 시작 값을 target으로 정의해주어 target과 taget 이후의 값들 사이 오차를 구해줘야 한다.

 

투포인터로도 풀 수 있었을 것 같으나, 이분 탐색에 대한 이해를 높이기 위해 사용해보았다.

 

제출코드

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

public class Main {
    static int N,M;
    static int A[];
    static int minVal = (int)1e11;
    static void binarySearch(int x){
        int start=x;
        int end=N-1;
        while(start<=end){
            int mid = (start+end)/2;
            if(A[mid]-A[x]>=M && minVal>A[mid]-A[x]){
                minVal=A[mid]-A[x];
            }

            if(A[mid]-A[x]==M) break;
            else if(A[mid]-A[x]>M){
                end=mid-1;
            }
            else{
                start=mid+1;
            }
        }
    }
    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 = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        A = new int[N];


        for(int i=0;i<N;++i){
            A[i]=Integer.parseInt(br.readLine());
        }
        Arrays.sort(A);

        for(int i=0;i<N;++i){
            binarySearch(i);
        }
        bw.write(minVal+"\n");
        bw.flush();
        bw.close();
    }
}