수고르기-2230번

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

2230번: 수 고르기

문제

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이상인 두 수를 고를 수 있다.

제한

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ 2,000,000,000
• 0 ≤ |A[i]| ≤ 1,000,000,000

 

package BaekJoon.TwoPointer;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 수고르기 {
	
	static int[]arr;
	static int n,m;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		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());
		}
		
	
		Arrays.sort(arr);
		int min = Integer.MAX_VALUE;
		
		for(int i=0; i<arr.length; i++) {
			
			int j = i+1;
			while(j<arr.length) {
			int diff = arr[j]-arr[i];
			
			if(diff>=m) {
			
				if(min>diff) {
					min=diff; //최소값보다 더 작을 때
					
				}
				break; //while문 벗어나서 i(left)를 늘려준다
			
			}
			else { //m 이상인것을 못찾을 경우
				j++; //j(right)를 늘려준다
			}
			
		}
		
		
	
	}
		System.out.println(min);
}
}

- 투포인터: 정렬을 하고 두개의 포인터로 원하는 값을 찾을 수 있는지 확인 해본다 -> right 포인터를 통해 차이를 늘릴수있다, left 포인터로 차이를 줄일 수있다.