[백준] 2230번 : 수 고르기

문제

 

 

접근 방식

두 수의 차이가 m 이상이면서 가장 작은 경우를 구해야 하는데

간단하게 이중 반복문으로도 풀 수는 있지만 입력의 크기를 생각하면

시간초과 때문에 다른 방법을 사용해야 한다.

 

골드 문제지만 투 포인터를 사용해서 풀면 간단하게 풀 수 있는 문제로

6개의 수가 주어졌을 때 차이가 3 이상인 수 중에서 가장 작은 경우를 찾아보겠다.

1 3 5 7 8 10

 

우선 위와 같이 주어진 수들이 정렬되어 있을 때

순서대로 비교할 기준을 처음인 1과 나머지 숫자들을 차이가 3 이상이 될 때까지 비교해보면

1 - 3 >> 2
1 - 5 >> 4

1 - 7 >> 6
1 - 8 >> 7
1 - 10 >> 9

 

5와 비교 했을 때 차이가 4로 처음으로 3보다 커지는데

이후의 비교는 차이가 점점 커지기 때문에 의미가 없다는 것을 알 수 있다.

 

그래서 차이가 처음으로 3보다 커진 경우에는 비교하는 기준 인덱스를

1에서 3으로 바꿔 준 후에 다시 비교를 해주면 된다.

3 - 5 >> 2
3 - 7 >> 4

 

3을 기준으로 비교하다 보면 마찬가지로 7과의 차이가 4일 때

기준이 다시 바뀌게 되고

5 - 7 >> 2
5 - 8 >> 3

 

5를 기준으로 다시 비교해보면 8과의 차이가 3으로

이후의 수들을 굳이 비교안해도 정답이 확실하기 때문에

탐색을 종료할 수 있다.

 

골드 문제지만 이렇게 투 포인터의 개념만 안다면 쉽게 풀 수 있다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		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 s = 0;
		int e = 1;
		int min = Integer.MAX_VALUE;

		while (e < n) {
			int minus = arr[e] - arr[s];
			if (minus == m) {
				min = m;
				break;
			}

			if (minus >= min) {
				s++;
				continue;
			}

			if (minus > m) {
				min = minus;
				s++;
			}
			else e++;
		}

		System.out.println(min);
	}
}