728x90
문제
N개의 정수로 이루어진 수열 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이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.
출력
첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.
풀이
먼저 들어온 수열을 오름차순으로 정렬한다.
이후 두 포인터를 이용하여 값을 계산하며 두 수의 차가 M보다 크며 기존에 존재하는 최대 차이가 나는 값보다 작을 경우
그 값을 정답으로 출력한다.
코드
import java.io.*;
import java.util.*;
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()), 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,e=0,ans=Integer.MAX_VALUE;
while(s<=e && e<n) {
if(arr[e]-arr[s]>=m) {
ans=Math.min(ans, arr[e]-arr[s]);
s++;
}
else
e++;
}
System.out.println(ans);
}
}
728x90
728x90
'Algorithm > Baekjoon' 카테고리의 다른 글
Baekjoon 10162 전자레인지 JAVA (0) | 2022.07.07 |
---|---|
Baekjoon 5585 거스름돈 JAVA (0) | 2022.07.07 |
Baekjoon 2576 홀수 JAVA (0) | 2022.07.07 |
Baekjoon 11724 연결 요소의 개수 JAVA (0) | 2022.07.07 |
Baekjoon 1057 토너먼트 JAVA (0) | 2022.06.21 |
댓글