[백준] P.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이상인 두 수를 고를 수 있다.

 

🖊️문제 풀이

투 포인터를 이용해 문제를 풀어주었다.

포인터 잡고 arr[left]와 arr[right]의 차이를 m이랑 비교하면서 결과를 도출했다.

처음에 좀 삽질했는데... right 값을 좀 잘못해서... 결국 해결하긴 했다!! 짝짝짝 박수

백준 투포인터로 분류된 문제를 한 네개...?정도 풀어봤는데 이제 좀 손에 익은 것 같다.

내일 하나 더 풀고!! 다른 알고리즘으로 넘어가야지

 

🖊️코드

package 투포인터;

import java.util.Arrays;
import java.util.Scanner;

public class P2230 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] arr = new int[n];

    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }

    Arrays.sort(arr);
    int left = 0;
    int right = 0;
    int answer = Integer.MAX_VALUE;
    while (left<=right && right<n){
      int tmp = arr[right]-arr[left];
      if (tmp >= m){
        answer = Math.min(answer,tmp);
      }

      if(tmp==m){
        break;
      }else if(tmp < m){
        right++;
      }else{
        left++;
      }
    }
    System.out.println(answer);
  }

}