[백준] Gold V. 수 고르기

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

 

사용 알고리즘

• 투 포인터

 

풀이

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 n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());


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

        int hi = 0;
        for(int lo = 0; lo < n; lo++) {
            while(hi < n && Math.abs(arr[hi] - arr[lo]) < m) {
                hi++;
            }

            if (hi == n) break;
            min = Math.min(min, Math.abs(arr[hi] - arr[lo]));
        }
        System.out.println(min);
    }
}

 

 

회고

 

Arrays.sort의 시간 복잡도는 O(nlogn)이고, n이 10만일 때도 충분히 제한 시간인 2초 안에 통과 가능하다.

 

투포인터 방식으로 풀었는데, 처음에 Math.abs(arr[hi] - arr[lo])의 값이 처음 m 이상일 때 루프를 빠져나와서 다른 경우의 수를 계산해주지 못하는게 아닐까 고민이 많았다.

 

ex) [1,2,3,4,5] 이고 m = 3일 때, [1,4]인 경우 루프를 탈출하고 [1,5]는 계산하지 않음.

 

그런데, 문제에서 찾는 것은 가장 차이가 작은 경우 이므로 뒤에 [1,5]는 굳이 계산을 할 필요가 없었다!! 하지만, 이렇게 계산을 하기 위해선 반드시 오름차순으로 정렬이 되어있어야 한다. 정렬을 하지 않고 제출했을 때 문제가 틀리는 것을 확인할 수 있었다.