[BaekJoon] 2230 수 고르기

1.  문제 링크

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

2.  문제

요약

• N개의 정수로 이루어진 수열에서 두 수를 골랐을 때, 그 차이가 M 이상이면서 제일 작은 경우를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작은 수열의 정수 개수 N과 0보다 크거나 같고 2,000,000,000보다 작거나 같은 M이 주어지고 두 번째 줄부터 N개의 줄에는 수열의 정수들이 주어집니다.
• 출력: 첫 번째 줄에 M 이상이면서 가장 작은 차이를 출력합니다.

3.  소스코드

첫 번째 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	public int getMinDif(int dif, int[] series) {
		Arrays.sort(series);
		int min = Integer.MAX_VALUE;
		for(int i = 0; i < series.length - 1; i++) {
			for(int j = i + 1; j < series.length; j++) {
				if(series[j] - series[i] < dif) {
					continue;
				}
				if(series[j] - series[i] >= dif) {
					if(min > series[j] - series[i]) {						
						min = series[j] - series[i];
					}
					break;
				}
			}
		}
		return min;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int num = Integer.parseInt(input[0]);
		int dif = Integer.parseInt(input[1]);
		int[] series = new int[num];
		for(int i = 0; i < num; i++) {
			series[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMinDif(dif, series) + "\n");
		bw.flush();
		bw.close();
	}
}

두 번째 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	public int getMinDif(int dif, int[] series) {
		Arrays.sort(series);
		int left = 0;
		int right = 0;
		int min = Integer.MAX_VALUE;
		while(right < series.length) {
			int difference = series[right] - series[left];
			if(difference < dif) {
				right++;
				continue;
			}
			if(difference == dif) {
				return dif;
			}
			left++;
			min = Math.min(min, difference);
		}
		return min;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int num = Integer.parseInt(input[0]);
		int dif = Integer.parseInt(input[1]);
		int[] series = new int[num];
		for(int i = 0; i < num; i++) {
			series[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMinDif(dif, series) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

첫 번째 풀이

• 주어진 수열을 오름차순으로 정렬한 후, 작은 수들의 경우부터 모든 경우를 해보면서 두 수의 차가 M보다 크거나 같은 수 중 가장 작은 수를 찾아갑니다.
• 수열을 오름차순으로 정렬하였기 때문에 한 수를 기준으로 다른 수의 크기를 키워나간다면 두 수의 차가 처음으로 M보다 크거나 같아졌을 때가 기준되는 수에 대하여 두 수의 차가 M보다 크거나 같은 수 중에서 가장 작은 수이기 때문에 해당 수를 발견했다면 더이상 기준되는 수의 나머지 경우는 확인하지 않아도 됩니다.

1. 주어진 수열을 오름차순으로 정렬합니다.
2. 두 수의 차가 M보다 크거나 같은 수 중 가장 작은 수를 저장하기 위한 변수 min을 생성합니다.
3. 수열의 가장 작은 수부터 2번째로 가장 큰 수까지 반복문을 돌면서 두 수의 차가 M보다 크거나 같은 수 중 가장 작은 수를 찾습니다.
   • 기준되는 수 바로 다음 수부터 마지막 수까지 확인하면서 두 수의 차가 M보다 크거나 같은 경우에 변수 min의 값이 두 수의 차보다 크다면 최소값을 두 수의 차로 변경하고 기준되는 수에 대한 남은 수들을 확인하지 않고 다른 수로 기준되는 수를 변경합니다.
4. 3번의 반복문이 끝났을 때의 변수 min값이 최소값이기 때문에 해당 수를 출력합니다.

두 번째 풀이

• 투 포인터를 이용하여 문제를 해결합니다.
• 주어진 수열을 오름차순 한 후에 두 포인터 모두 처음 수부터 시작하여 왼쪽 포인터에 해당하는 수열에서의 수와 오른쪽 포인터에 해당 수열에서의 수의 차를 확인하여 차가 M보다 작다면 차를 키워야하기 때문에 오른쪽 포인터를 더 큰 수로 이동시킵니다.
• 차가 M과 같다면 M보다 크거나 같은 수를 구하는 것인데 이러한 상황에서 M이 가장 작은 수이므로 다른 경우를 확인하지 않습니다.
• 위 두 경우 모두 아니라면 즉 차가 M보다 크다면 차를 줄여야하기 때문에 왼쪽 포인터를 더 큰 수를 이동시킵니다.

1. 주어진 수열을 오름차순으로 정렬합니다.
2. 왼쪽 포인터를 나타내는 left 변수와 오른쪽 포인터를 나타내는 right 변수를 생성하고 0으로 초기화하며 두 수의 차가 M보다 크거나 같은 수 중 가장 작은 수를 나타내는 변수 min을 생성하고 최댓값으로 초기화합니다.
3. 오른쪽 포인터가 수열의 마지막 수에 도달할 때까지 반복문을 돌며 차가 M보다 크거나 같은 수 중 가장 작은 수를 찾습니다.
   1. 왼쪽 포인터에 해당하는 수와 오른쪽 포인터에 해당하는 수의 차를 구합니다.
   2. 두 수의 차가 M보다 작다면 차를 키우기 위해 오른쪽 포인터를 오른쪽으로 1 이동시킵니다.
   3. 두 수의 차가 M이라면 M보다 크거나 같은 수 중 M이 가장 작은 수이므로 반복문을 나와서 M을 출력합니다.
   4. 두 수의 차가 M보다 크다면 차를 줄이기 위해 왼쪽 포인터를 오른쪽으로 1 이동시키고 변수 min의 값을 두 수의 차와 min의 값 중 더 작은 값으로 설정합니다.
4. 3번의 반복문이 끝났을 때의 변수 min값이 최소값이기 때문에 해당 수를 출력합니다.