[BOJ] 수 고르기 (Java)

 

문제 링크

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

 

문제 이해

이 문제를 읽고 이분 탐색이 가장 먼저 생각났다. 이분 탐색으로 풀어도 어렵진 않았을 것 같은데, 나는 투포인터의 개념으로 풀었다.

다만, 투포인터를 쓸 때 start = 0 / end = size - 1 로 풀었었는데, 이번 경우는 start += 1 / end -= 1을 갱신하는 포인트가 애매하다고 생각했다.

이번 풀이는 start = 0 / end = 0 초기화된 상태에서 시작했다.

따라서 distance가 M보다 클 경우는 start를 높이면서 distance의 최숫값을 갱신하려고 했다.

그리고 distance가 M보다 작을 경우는 end를 키우면서 distance의 간격을 높여서 찾고자 했다.

기준값만 잘 두면 어렵지 않았던 문제였다.

 

예제

5 3
1
6
3
7
2
결과 : 3

 

코드

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * BOJ_2230_수고르기
 *
 * N개의 정수로 이루어졌다.
 * 수열에서 두 수를 골랐을 때 그 차이가 M이상이면서 제일 작은 경우
 * {1, 2, 3, 4, 5}
 *
 * 1, 3, 5
 * 5 - 1 = 4
 * 3 - 1 = 2
 *
 * */
public class BOJ_2230_수고르기 {

    static BufferedReader br;
    static StringTokenizer st;

    static int N;
    static int M;
    static int [] list;
    static int min;

    private static void simulation() {
        int start = 0;
        int end = 0;

        min = Integer.MAX_VALUE; // 가장 작은 값

        while (start < N  && end < N) {
            int distance = list[end] - list[start];

            if (distance >= M) {
                min = Math.min(distance, min);
                start += 1;
            } else {
                end += 1;
            }
        }
    }

    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine().trim());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        list = new int [N];
        for (int idx = 0; idx < N; idx ++) {
            list[idx] = Integer.parseInt(br.readLine().trim());
        }

        Arrays.sort(list);
        simulation();
        System.out.println(min);
    }
}