반응형
문제
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이상인 두 수를 고를 수 있다.
예제 입력
예제 출력
접근
투포인터 알고리즘으로 간단하게 풀 수 있을 줄 알았지만...?! 않이 자꾸 오답이 뜨길래 정렬을 해주고 하니까 정답이 나왔다...
정렬 정렬 정렬이 뭐라고...
코드
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 SelectNum_2230 {
static int N, M;
static int[] arr;
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());
N = Integer.parseInt(st.nextToken()); // 수열의 원소의 수
M = Integer.parseInt(st.nextToken()); // 두 수를 골랐을 때, 만족해야 하는 차이의 최솟값
arr = new int[N];
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(br.readLine()); // 1 5 3, 1 2 3 4 5 (M=3)
}
Arrays.sort(arr);
int lo=0, hi=0, result=Integer.MAX_VALUE;
while(hi < N) {
if(arr[hi] - arr[lo] < M) {
hi++;
continue;
}
if(arr[hi] - arr[lo] == M) {
result = M;
break;
}
result = Math.min(result, arr[hi]-arr[lo]);
lo++;
}
if(result == 200000001) {
bw.write(0+"\n");
}else {
bw.write(result+"\n");
}
bw.flush();
br.close();
bw.close();
}
}
반응형
'알고리즘 > [ Baekjoon ]' 카테고리의 다른 글
[ Baekjoon ][JAVA][1789] 수들의 합 (0) | 2020.09.22 |
---|---|
[ Baekjoon ][JAVA][1365] 꼬인 전깃줄 (0) | 2020.09.21 |
[ Baekjoon ][JAVA][2531] 회전초밥 (5) | 2020.09.20 |
[ Baekjoon ][JAVA][1806] 부분합 (0) | 2020.09.20 |
[ Baekjoon ][JAVA][2042] 내려가기 (0) | 2020.09.20 |