[백준/C++] 2230번. 수 고르기

[백준/C++] 2230번. 수 고르기

1. 문제

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이 된다.

2. 입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.

2-1. 제한

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

3. 출력

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

4. 풀이

• 투 포인터 문제
• start와 end 두 개의 포인터를 조작해서 답을 찾는다.
• 배열을 먼저 정렬해야 한다.
• 앞에서부터 두 수를 고른다. (start = 0, end = 0)
  • 같은 수를 고를 수 있기 때문에 둘 다 0으로 초기화
• 두 수의 차가 원하는 결과보다 작다면 차를 늘려야 한다.
  • (큰 수 - 작은수)에서 큰 수를 증가 시켜야 차가 늘어난다.
  • end를 증가시키면 큰 수가 증가한다.
• 두 수의 차가 원하는 결과보다 크거나 같다면 차를 줄여야 한다.
  • 두 수의 차가 원하는 결과보다 크거나 같고 기록된 최솟값보다 작다면 최솟값을 갱신한다.
  • (큰 수 - 작은수)에서 작은 수를 증가 시켜야 차가 줄어든다.
  • start를 증가시키면 작은 수가 증가한다.

5. 처음 코드와 달라진 점

• INF를 987654321로 설정했는데 충분하지 않았다.
• INF를 2000000000로 변경했다.

6. 코드

#include <iostream>
#include <algorithm>
#define INF 2000000000

using namespace std;

int n, target;
int arr[100000];

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin >> n >> target;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }

  sort(arr, arr+n);

  int start = 0, end = 0;
  int answer = INF;
  while (start < n && end < n) {
    int result = arr[end] - arr[start];
    if (result < target) {
      end++;
    }
    else {
      answer = min(answer, result);
      start++;
    }
  }
  cout << answer;
}```