BOJ 2230 수 고르기

신현철·2022년 10월 16일

알고리즘

BOJ

목록 보기

6/9

2230번:수 고르기

🔍 문제분석

입력

먼저 N,M이 주어진다.
이후 한 줄에 하나씩 정렬되지 않은 수열 A의 원소들이 주어진다.

구현

두 수를 고른다는 점에서 우선 투 포인터 풀이라고 힌트를 얻을 수 있다.

투 포인터 풀이를 떠올렸다면, 입력이 정렬되지 않고 들어오기 때문에 정렬을 먼저 진행해야한다고 생각할 수 있다.

출력

M 이상인 최소의 차를 출력한다.

💡 구현 분석

포인터 두 개를 각각 lo,hi라고 설정해보자.

lo,hi는 각각 고른 두 수 중 작은 수, 큰 수를 나타낸다.

풀이를 진행하는 경우 idx보다는 종료조건이 중요하므로 while으로 풀이를 진행한다.

그렇다면 종료 조건을 생각해보자.

종료 조건

lo가 hi를 역전한 경우

hi가 배열 끝에 도달한 경우

이 정도가 된다. 따라서 while 문의 조건은

while( lo <= hi && hi < N)

위처럼 될 것이다.

어째서 lo <= hi 일까?
두 수를 고르는데 lo와 hi가 같다면 말이 안되지 않을까?

그렇다. 말이 안된다. 하지만 그렇다고 탐색을 종료해버리면 WA를 받는다.

lo가 hi를 따라잡더라도, hi를 증가시키면 최적해를 얻을 가능성이 존재하기 때문이다.

따라서 역전만 되지 않으면 된다.

부분최적해 저장

현재까지 탐색한 답이 전체 문제의 최적해가 아닐 수 있다. 따라서 임시로 부분최적해를 저장할 공간이 필요하다. 부분 최적해는 차를 저장해도 좋지만, 나의 경우엔 lo, hi값을 ansLo, ansHi에 저장했다.

이 때 기존 부분최적해보다 새로 찾은 부분최적해가 M 이상이면서 크기가 작아야하며, hi와 lo가 달라야한다.

포인터 이동

lo를 증가시키는 조건, hi를 증가시키는 조건 두 가지를 생각하면 된다.

현재 두 수의 차가 M 초과라면, 차를 더 줄여야하므로 lo를 증가시킨다.
현재 두 수의 차가 M 미만이라면, 차를 더 늘려야하므로 hi를 증가시킨다.

추가적으로 두 수의 차가 M 보다 작은 최적해는 존재하지 않으므로, M일 때 종료시킨다.

✅ 정답 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int N, M;
vector<int> A;

void input(){
    cin >> N >> M;
    int i = N, tmp;
    while (i--){
        cin >> tmp;
        A.push_back(tmp);
    }
}

int search(){
    int lo = 0, hi = 1;

    int ansLo = 0, ansHi = N - 1;

    while (lo <= hi && hi < N){
        if(hi != lo && A[hi] - A[lo] <= A[ansHi] - A[ansLo] && A[hi] - A[lo] >= M){
            ansLo = lo;
            ansHi = hi;
        }

        int tmp = A[hi] - A[lo];

        if (tmp == M)
            break;
        if (tmp < M)
            hi += 1;
        else
            lo += 1;
    }

    return A[ansHi] - A[ansLo];
}

void solution(){
    input();
    sort(A.begin(), A.end());
    cout << search() << '\n';
}

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

    solution();
}