[백준] 2230 - 수 고르기 (C++)

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

N개의 정수로 이루어진 수열 A[1], A[2], ..., A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ 2,000,000,000
• 0 ≤ |A[i]|  ≤ 1,000,000,000
• 항상 차이가 M 이상인 두 수를 고를 수 있다.

 

N의 최댓값이 100,000이기 때문에 이중 for문을 돌릴 경우 시간 초과가 날 수 있다. 우선 배열을 입력받은 뒤 정렬하고, 투 포인터를 통해 두 수의 차이가 M 이상일 때의 최솟값을 구한다. 반복문을 진행하다 보면 right 값이 N을 넘어갈 수 있으므로 if문을 통해 반복문을 빠져나올 수 있게 해야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M, A[i] 입력받기
2. A[i] 오름차순으로 정렬하기
3. 투 포인터로 두 수의 차이를 구하면서, 차이가 M 이상일 때 ans 값을 갱신하기
4. ans 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n,m,arr[100000],ans=2000000000;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i=0; i<n; i++) cin >> arr[i];
    sort(arr,arr+n);

    int l=0,r=0;
    while (l<=r) {
        if (r>=n) break;
        int tmp = arr[r] - arr[l];
        if (tmp>=m) {
            ans = min(ans,tmp);
            l++;
        }
        else {
            r++;
        }
    }
    
    cout << ans;
}