[BOJ] 백준 2230번 : 수 고르기 (JAVA)

문제

N(1≤N≤100,000)개의 수로 이루어진 수열 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이 된다.

입력

첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다.

출력

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

 

풀이

알고리즘 분류 상 정렬로 되어있긴 했지만, 단순한 정렬 문제는 아니었다고 생각합니다. 총 2가지 방법으로 풀 수 있었는데, 첫 번째는 '투 포인터 알고리즘'이고, 두 번째는 '이분 탐색'입니다.

풀이에 설명하기에 앞서, 배열 A[i]가 음수도 들어올 수 있다는 점을 주의하시길 바랍니다. 저는 절댓값이 씌어져있는 것을 보지 못하고 풀었다가 삽질을 오래 했습니다..

먼저, 투 포인터 알고리즘을 사용한 풀이부터 보겠습니다.

 

풀이 - 투 포인터

투 포인터에 생소하신 분은 아래 포스팅 글을 읽고 오시길 바랍니다. 꽤나 설명이 잘 되어있는 블로그입니다.

https://m.blog.naver.com/kks227/220795165570

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

쉽게 말하면, 선을 2개 설정해서 특정 조건에 의해 선을 움직인다는 느낌입니다. 아래 예제를 통해서 이 알고리즘을 어떻게 적용시키는 것인지 알아봅시다.

 

예제

N = 3, M = 2

A = {1, 4, 3, 2, 5}

먼저, 오름차순으로 정렬하면, A = {1, 2, 3, 4, 5}가 됩니다. 이제, 아래 그림을 봅시다.

 

 

주황색 선은 i, 빨간색 선은 j라 표현하겠습니다. 그리고 A[i] - A[j] >= M을 만족하는지 순차적으로 체크하는 것이 핵심입니다.

현재 A[0] - A[0] = 0이고, 이것은 M보다 작으므로 i를 1 증가시켜서 오른쪽으로 이동시킵니다.

 

 

A[1] - A[0] = 1이므로 M보다 작습니다. 마찬가지로 i를 1 증가시켜서 주황색 선을 오른쪽으로 이동시킵니다.

 

 

A[2] - A[0] = 2이므로 M보다 작거나 같습니다. 따라서, ans와 같은 변수에 Math.min(ans, A[2] - A[0]) 식을 처리해 주면 됩니다. ans = Integer.MAX.VALUE로 설정했다고 가정하면, 위 경우에 ans = 2로 초기화됩니다.

그리고 이렇게 A[i] - A[j] >= M을 만족시킬 경우, j를 1 증가시켜서 빨간색 선을 오른쪽으로 이동시킵니다.

 

 

A[2] - A[1] = 1로 M보다 작습니다. 따라서 i만 1 증가시켜서 주황색 선을 오른쪽으로 이동시킵니다.

 

 

A[3] - A[1] = 2로 M보다 작거나 같습니다. 따라서 ans = 2로 그대로 초기화 됩니다. 이번에는 j를 1 증가시켜서 빨간색 선을 오른쪽으로 이동시킵니다.

 

A[3] - A[2] = 1이므로 M보다 작습니다. 따라서 i를 1 증가시켜서 주황색 선을 오른쪽으로 이동시킵니다.

 

 

A[4] - A[2] = 2로 M보다 작거나 같습니다. 따라서 ans = 2로 초기화되고, j를 1 증가시켜서 빨간색 선으로 오른쪽으로 이동시킵니다.

 

 

A[4] - A[3] = 1로 M보다 작습니다. 따라서 i를 1 증가시켜야합니다. 하지만, i는 배열의 맨 끝 부분에 도달했으므로 투 포인터 작업을 종료합니다.

그리고 ans를 반환하면, 그것이 바로 정답이 됩니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

소스코드 - 투 포인터

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
 
        int i = 0, j = 0;
        int ans = Integer.MAX_VALUE;
        // 투 포인터 알고리즘
        while (i < N) {
            if (arr[i] - arr[j] < M) {
                i++;
                continue;
            }
 
            if (arr[i] - arr[j] == M) {
                ans = M;
                break;
            }
 
            ans = Math.min(ans, arr[i] - arr[j]);
            j++;
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

풀이 - 이분탐색1

이번에는 이분탐색을 이용한 풀이입니다. 정확히는 Lower Bound를 이용하려고 합니다. Lower Bound는 이분탐색에서 '찾으려는 수 이상의 값 처음으로 나오는 위치'를 구하는 알고리즘을 말합니다.

(반대로, Upper Bound는 '찾으려는 수보다 큰 값이 처음으로 나오는 위치'를 구하는 알고리즘입니다.)

예를 들어, A = {1, 2, 4}에서 3을 찾으려고 하면 3보다 큰 4가 해당하는 위치인 2가 반환될 것이고, 2를 찾으려고 하면 2가 해당하는 위치인 1이 반환될 것입니다.

우리가 구하려는 것은 i가 주어졌을 때, A[x] - A[i] >= M을 만족하는 x를 구하는 것입니다. 그리고 Upper Bound가 아니라, Lower Bound를 사용하는 이유는 간단합니다. 이분탐색을 통해서 A[x] - A[start] == M에 해당하는 x 위치를 찾는 것이 최적인데, 차이가 딱 M이 아니라 그것보다 클 수도 있기떄문이죠.

Lower Bound와 Upper Bound의 코드는 아래 블로그에서 자세히 알아보실 수 있습니다.

https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=221045300639&proxyReferer=https:%2F%2Fwww.google.com%2F

Upper Bound(상계), Lower Bound(하계)

 

위 블로그에서 사용된 Lower Bound 함수를 적절히 응용하시면 됩니다.

아래는 위 내용을 정리한 소스코드입니다.

 

소스코드 - 이분탐색1

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
 
        int ans = Integer.MAX_VALUE;
 
        int start = 0, end = 0;
        int mid = 0;
        for (int i = 0; i < N; i++) {
            start = i;
            end = N;
 
            while (start < end) {
                mid = (start + end) / 2;
                if (arr[mid] - arr[i] < M) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
 
            if (end == N) {
                continue;
            }
 
            ans = Math.min(ans, arr[end] - arr[i]);
 
            if (ans == M) {
                break;
            }
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

풀이 - 이분탐색2

이분탐색을 이용하여 문제의 조건에 맞게 더 빠른 Lower Bound를 구현할 수도 있습니다. 여기서 키 포인트는 start와 end가 같아지는 점을 찾는 것입니다. 만약에, arr[mid] - arr[start] = M이라면, 이 차이가 최소이기때문에 ans = M으로 처리하고 반복문 자체를 종료시키면 되지만, M과 같지 않을 경우는 M보다 큰 최소의 차이 값을 찾아주어야 합니다.

이 때, start와 end의 이분탐색 움직임을 살펴보면, start와 end가 같아지는 순간이 있습니다. 그리고 그 위치가 바로 최적의 위치죠.

예를 들어, A = {1, 2, 5}이고, M = 2인 경우를 봅시다.

start = 0, end = 3일 때, mid = 1이 됩니다. A[mid] - A[start] = 1이므로 M보다 작습니다. 이 경우에는 start = mid + 1 = 2로 처리해 줍니다. 그리고 mid = (2 + 3)  / 2 = 2, A[mid] - A[start] = 4가 됩니다. M보다 4가 크기 때문에 end = mid = 2로 초기화합니다. start와 end가 일치하는 이 위치가 바로 최소입니다. 여기서 ans = Integer.MAX.VALUE로 초기화되어있다고 가정하면, ans = Math.min(ans, A[start] - A[i]) = 4가 됨을 알 수 있습니다.

'이분탐색1'처럼 구해도 되지만, start와 end가 같아지는 지점을 주목함으로써 Lower Bound를 구할 수 있다는 사실을 알아두시면 되겠습니다.

아래는 위 내용을 정리한 소스코드입니다.

 

소스코드 - 이분탐색2

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
 
        int ans = Integer.MAX_VALUE;
 
        int start = 0, end = 0;
        int mid = 0;
        for (int i = 0; i < N; i++) {
            start = i;
            end = N;
 
            while (start != N) {
                mid = (start + end) / 2;
 
                if (arr[mid] - arr[i] == M) {
                    ans = M;
                    break;
                }
 
                if (arr[mid] - arr[i] < M) {
                    start = mid + 1;
                } else if (start == end) {
                    ans = Math.min(ans, arr[start] - arr[i]);
                    break;
                } else {
                    end = mid;
                }
            }
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.