BOJ 2230 - 수 고르기

 

 

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

2230번: 수 고르기

 

 

• N개의 정수로 이루어진 수열 A (1 ≤ N ≤ 10만)
• 수열 A의 각 원소는 (0 ≤ |A[i]| ≤ 10억)
• 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우 (0 ≤ M ≤ 20억)

 

아이디어

배열 A에서 두 수를 골라서 차이가 M 이상인 경우를 찾기 위해 먼저 모든 경우의 수를 생각해 봤다. 

배열 A를 오름차순 정렬 후 이중 for문으로 모든 차이를 구해서 가장 작은 차이를 갱신하면 답을 구할 수 있다.

 

for (int i = 1; i <= N; i++) {
    for (int j = i; j <= N; j++) {
        if (A[j] - A[i] >= M) {
            ans = Math.min(ans, A[j] - A[i]);
            break;
        }
    }
}

 

이렇게 하면 풀리기는 풀리지만 시간이 오래 걸린다. 

 

더 빠르게 풀기 위해 A 배열을 오름차순으로 정렬한 후 Left와 Right 투 포인터를 활용하여 A[Right]와 A[Left]의 차이 비교해준다.

• A[Right]와 A[Left] 차이를 비교했을 때 M보다 작으면 고려할 대상이 아니므로 R++로 넘어간다. 
• 차이가 M이상인 경우 ans를 갱신해준 후 L++로 다음 경우로 넘어간다.

ans = Integer.MAX_VALUE;
int R = 1;

for (int L = 1; L <= N; L++) {

    // 필요한 만큼 R 이동
    while (R + 1 <= N) {
        // M 이하인 경우는 R을 이동시켜서 건너뛰기
        if (A[R] - A[L] < M) {
            R++;
        // M 이상일 경우 정답갱신하러 ㄱㄱ
        } else {
            break;
        }
    }

    // 정답 갱신
    // 현재 R 포인터의 뒤쪽은 어짜피 차이가 커질테니 상관 X
    if (A[R] - A[L] >= M) {
        ans = Math.min(ans, A[R] - A[L]);
    }

}

 

이렇게 하면 훨씬 빠른 속도로 적은 경우의 수만 고려해서 풀 수 있다. 

 

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M, ans;
    static int[] A;

    static void init() 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());

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

    static void pro() throws IOException {
        Arrays.sort(A, 1, N+1);

        ans = Integer.MAX_VALUE;
        int R = 1;

        for (int L = 1; L <= N; L++) {

            // 필요한 만큼 R 이동
            while (R + 1 <= N) {
                // M 이하인 경우는 R을 이동시켜서 건너뛰기
                if (A[R] - A[L] < M) {
                    R++;
                // M 이상일 경우 정답갱신하러 ㄱㄱ
                } else {
                    break;
                }
            }

            // 정답 갱신
            // 현재 R 포인터의 뒤쪽은 어짜피 차이가 커질테니 상관 X
            if (A[R] - A[L] >= M) {
                ans = Math.min(ans, A[R] - A[L]);
            }

        }

        bw.write(ans+" ");
    }

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

        pro();

        bw.close();
    }

}