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

 

 

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

 

---

 

 

요새 코드적인 감각이 조금 사라진 것 같아서 구현 문제를 풀어보았다. 

 

비동기식 구조와 SpringBoot를 함께 병행하며 실습 위주로 하다보니 근본적인 코드 짜는 능력이 현저히 퇴화된 것을 느껴버렸다.

 

그래서 하루에 1개는 아니더라도 2일 1개를 목표로 자바로 간단하게 풀어볼 예정이다.

 

---

 

위의 문제는 백준 기준 골드 5의 문제이며 문제의 이해는 꽤 간단하지만 알고리즘적으로 짜는 방식을 익히고 구현을 보는 문제인거 같다.

 

사용되는 알고리즘은 핵심적인 투 포인터를 묻는 문제인거 같다.

 

 

문제 접근 

 

1.  N 과 M 그리고 그에 해당되는 수열의 값들을 먼저 받는다. 이때 문제에서 나온 [1,5,3]을 예로 들어보자.

M이 받은 입력 값은 3

 

각 두 수를 골라 뺀 값이 입력 받은 3보다 높은 수를 출력하는 것이 목표.

 

 

- 생각한 방법 중 최고였던 것.

 

Bad : 임의 두 수 중에 큰 값을 모른채로 두 수를 빼고 난 후에 절댓값을 씌우는 것.

Good : 오름차순으로 정렬하여 큰 값에서 작은 값을 그냥 빼서 양수 값을 반환 시키는 것.

 

 

2. [1,5,3] 을 오름차순으로 정렬 후에 M값과 비교한다.

 

1,3,5 > 

 

3 - 1 = 2

 

5 - 3 = 2

 

5 - 1 = 4

 

이렇게 되면 M값보다 큰 5 - 1 = 4 값이 나오게 된다.

 

 

3. 두 수를 빼서 비교한 값 중에서 M값 이상이며 최솟값을 반환 시킨다.

 

 

 

- 문제를 풀면서 힘들었던 것

 

반환 과정에서 exit 처리와 필요한 알고리즘을 제대로 사용하지 않아 런타임에러 NZEC ( Non Zero Exit Code )를 받은 것.

 

자바 특징 중에서 하나는 굳이 0으로 반환하지 않아도 내부적으로 0 반환을 해준다는 것인데 1을 그냥 반환해버리니깐 그냥 런타임 에러를 잔뜩 받음.

 

 

 

핵심적인 알고리즘은 투 포인터를 사용했던 것.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
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));
        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 left = 0;
        int right = 1;
        int answer = Integer.MAX_VALUE;

        while (right < N) {
            int diff = arr[right] - arr[left];

            if (diff == M) {
               
                System.out.println(M);
                return;
            } else if (diff > M) {
                answer = Math.min(answer, diff);
                left++;
                if (left == right) {
                    right++;
                }
            } else {
                right++;
            }
        }

        System.out.println(answer);
    }
}