[백준] 2230번 수 고르기

문제: 2230번: 수 고르기

basic-algo-lecture/workbook/0x14.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x14.md at master · encrypted-def/basic-algo-lecture

 

• 이분탐색 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;

int m;

int binarySearch(int target, int st_, vector<int>& nums) {
    int st = st_;
    int en = nums.size() - 1;

    int answer = 2147483647;
    while (st <= en) {
        int mid = (st + en) / 2;

        if (abs(nums[mid] - target) >= m) {
            answer = nums[mid];
            en = mid - 1; // 차이를 더 줄여야 하니깡
        }
        else if (abs(nums[mid] - target) < m) {
            // 차이를 키워야행..
            st = mid + 1;
        }
    }
    return answer;
}

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

    int n;
    cin >> n >> m;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    sort(nums.begin(), nums.end());

    int answer = 2147483647;
    for (int i = 0; i < n - 1; i++) {
        int near = binarySearch(nums[i], i + 1, nums);

        if (abs(nums[i] - near) < answer)
            answer = abs(nums[i] - near);
    }
    cout << answer;

    return 0;
}

 

일단 강의에서 이분탐색으로 풀어보라길래 풀었는데 맞았다. 이제 투포인터로 푸는 방법 강의로 배우러 가야딩 ~_~

 

 

• 투 포인터 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(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 st = 0;
    int en = 0;
    int ans = 2147483647;
    while (en < n) {
        if (abs(nums[en] - nums[st]) >= m) {
            if (ans > abs(nums[en] - nums[st])) {
                ans = abs(nums[en] - nums[st]);             
            }
            // 둘의 차이가 m 보다 크거나 같으면 st 증가
            st++;
        }
        else {
            // 둘의 차이가 m 보다 작으면 en 증가
            en++;
        }
        // st 가 en 보다 커지면 안 됨
        if (st > en) {
            en = st;
        }
    }
    cout << ans;

    return 0;
}

 

아나 처음 풀이 때 if (st > en) 부분을 안 넣어줘서 틀렸다. st 값이 en 보다 커지면 안 되는데 이걸 빼먹다니..;;

 

 

암튼 두 풀이법 다 재밌는 것 같다. 확실히 시간상 더 효율적인 건 투포인터인듯?