Two Pointers: 백준 수 고르기-2230

문제 유형: Two Pointers

수 고르기

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.

예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

 

작성 코드

import java.util.Arrays;
import java.util.Scanner;

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

    public static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        givenNums = new int[N];
        for (int i = 0; i < N; i++) {
            givenNums[i] = sc.nextInt();
        }
        Arrays.sort(givenNums);
    }

    public static void pro() {
        int gap = Integer.MAX_VALUE;
        int j = 0;
        for (int i = 0; i < givenNums.length; i++) {
            while (givenNums[j] - givenNums[i] < M && j < N - 1) {
                j++;
            }
            int current = givenNums[j] - givenNums[i];
            if (current >= M) gap = Math.min(current, gap);
        }
        System.out.println(gap);
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}

접근 방식

1. 일전에 풀었던 부분합과 유사한 방식으로 접근했다. 대신 이번의 경우 그 기준이 합이 아니라 차이로 지정했다. 

개선 사항

1. 부분화과 유사하다는것을 알 고 있었음에도 오랜 시간이 걸렸다. for 문 안의 while 문 구조를 외우는 것도 방법이라는 생각이 든다.