[240322] 알고리즘 리부트 36일차 - 백준 2230 자바

[Part2-Chapter01-Clip03]

- 백준 2230 수 고르기

left가 되는 인덱스를 기준으로 반복문을 돌면서  그 안에서  while 문으로 right를 맨 마지막 인덱스로부터 줄여보려고 했다. 하지만 left가 바뀔 때마다 right를 새로이 맨 마지막 인덱스로 갱신했기 때문에 결국 n^2이 되어 시간 초과가 발생했다. 음 그러면 right는 이전 left가 옮겨 놓은 그 위치 그대로 탐색해보자고 했지만 값을 못 찾는 문제가 발생했다. 이번 left와 right를 각각 확인해봐야 하는데 이미 right를 당겨와 버려서 그 뒤의 값들와 left를 비교하지 못하는 문제였다.

다시 생각해보니 방향이 틀렸다는 것을 깨달았다. 마주보는 방향으로 이동하는 것이 아니라 한 방향에서 시작하면서 m보다 작으면 right를 늘려주고 m보다 크면 찾고자하는 값의 후보이니 min에 담아준 뒤에 다시 더 작은 값은 없을지 left를 늘려서 right는 고정한 채로 다음 값을 찾는 것이다. 여기서 뒤로 갈 필요가 없는 것은 오름차순으로 정렬했기 때문에 그보다 더 큰 차를 가질 수밖에 없다는 것을 알 수 있다. 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);
        //System.out.println(Arrays.toString(arr));

        long min = Long.MAX_VALUE;
        int left = 0;
        int right = 0;

        while (left < n && right < n) {
            //System.out.printf("left는 %d, right는 %d", left, right);

            if (arr[right] - arr[left] == m) {
                //System.out.println("m과 같아요");
                min = (arr[right] - arr[left]);
                //System.out.println("min: " + min);
                break;
            } else if (arr[right] - arr[left] > m) {
                min = Math.min(arr[right] - arr[left], min);
                left++;
                //System.out.println("left 늘렸어요 min: " + min);
            } else {
                right++;
                //System.out.println("right 늘렸어요");
            }

        }
        System.out.println(min);
    }


}