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

 

🔗 문제 링크 : https://www.acmicpc.net/problem/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

 

 

 

입출력 예시

 

 

 

---

 

풀이 #1 | 투포인터(Two Pointer) 방식

투포인터를 이용하여 문제를 해결했다.

 

• left 포인터가 하나씩 증가하면서, 조건을 만족할 때까지 right 포인터를 계속 움직인다.
• 최소값을 저장할 minDiff 변수의 초기값은 제일 큰 수 0x7fffffff를 저장해 놓고 이후 비교를 통해 최솟값을 갱신한다.

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

int main() {
    ios_base::sync_with_stdio(0);
    int N, M;
    cin >> N >> M;
    vector<int> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());

    int right = 0;
    int minDiff = 0x7fffffff;
    for (int left = 0; left < N; left++) {
        while (right < N && nums[right] - nums[left] < M) 
            right++;
        if (right == N) break;
        minDiff = min(minDiff, nums[right] - nums[left]);
    }

    cout << minDiff;
}

 

아래 풀이와 비교를 위한 실행시간 결과

 

 

 

풀이 #2 | 이중 for문을 이용한 풀이

이중for문으로도 해결이 가능하나, 이 방법은 right가 left에 대해 right를 그때그때마다 다시 왼쪽에서부터 찾기 때문에 시간복잡도가 투포인터에 비해 매우 증가한다. 

투포인터는 right 포인터가 이미 검사한 부분을 다시 탐색하지 않기 때문에 속도가 훨씬 빠르다.

 

위의 투포인터 풀이 전에 이중 for문으로 먼저 풀었지만, 수행 시간이 2000ms 가까이 되는 것을 보고 맞은 게 맞은 거 같지 않은 찝찝한 기분이.. 이후 투포인터 방식을 이용해 다시 풀어냈다.🤣

❗

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

int main() {
    ios_base::sync_with_stdio(0);
    int N, M;
    cin >> N >> M;
    vector<int> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());
    
    int minDiff = 0x7fffffff;
    for (int left = 0; left < N - 1; left++) {
        for (int right = left + 1; right < N; right++) {
            if (nums[right] - nums[left] >= M) {
                minDiff = min(minDiff, nums[right] - nums[left]);
                break;
            }
        }
    }

    cout << minDiff;
}

 

 

 

---