백준 2230번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	골드 5

사진을 클릭하면 문제로 이동합니다.

---

풀이

 밀린 문제 정리하기. 이 문제는 두가지 풀이가 존재한다. 첫번째 풀이는 투포인터이고, 두번째 풀이는 이분탐색이다. 사실 이 문제를 예전에 풀었을때에는 투포인터로 풀어냈고, 정리하려고 문제를 다시 봤을때에는 이분탐색으로 풀어냈다.

 

 우선, 문제를 읽어보고 알 수 있지만, 수열의 원소의 순서는 크게 중요하지 않다. 따라서, 정렬을 해주었다. 투포인터가 됐던, 이분탐색이 됐던 정렬을 해주는게 용이하기 때문이다.

 

 투포인터 풀이는 l, r 포인터를 모두 0에 위치시킨다. 두 원소의 차이가 m 이하라면 r 포인터를 오른쪽으로 한칸 옮긴다. m보다 크다면 l포인터를 오른쪽으로 옮긴다. r이 수열의 맨 끝에 왔다면, a[r]-a[l]의 차이가 m보다 작아질때까지 계속해서 답을 조사한다.

코드1 - 투포인터

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

int n, m;
vector<int> v;

void input() {
    cin >> n >> m;
    v.resize(n);
    for(int& x : v) cin >> x;
    sort(ALL(v));
}

void sol() {
    int l = 0, r = 0, answer = INT32_MAX, diff = 0;
    while(l <= r) {
        if (diff >= m) diff = v[r] - v[++l];
        else if (r == n - 1 && diff < m) break;
        else diff = v[++r] - v[l];
        if (diff >= m) answer = min(answer, diff);
    }
    cout << answer;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    input();
    sol();
}

 

이분탐색 풀이는 정렬된 수열의 원소를 하나씩 살펴보며, 해당 원소에 m을 더한 값 이상의 값이 수열에 있는지 살펴본다. 있다면 두 원소의 차이를 저장한다. 만약 찾지 못한다면, 더이상 탐색할 이유가 없다는 뜻이기 때문에 탐색을 종료한다.

코드2 - 이분탐색

// 입력부분 및 main함수는 코드1과 동일

void sol() {
    int answer = INT32_MAX;
    for(auto iter = v.begin(); iter != v.end(); ++iter) {
        auto k = lower_bound(iter, v.end(), *iter+m);
        if(k == v.end()) break;
        answer = min(*k-*iter, answer);
    }
    cout << answer;
}

위 : 이분탐색, 아래 : 투포인터