백준 2230 수 고르기 | C++

 

 

이번 포스팅은 백준 2230번 수 고르기입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/2230

2230번: 수 고르기

 

 

 

기본 알고리즘

투 포인터

 

 

셸 정렬 사용함

벡터와 sort 함수를 사용하면 코드의 길이와 실행 시간을 단축할 수 있다.

 

 

 

 

 

전체 코드

 

//백준2230 수 고르기                                                        
#include <iostream>
using namespace std;
 
void sortGapInsertion(int list[], int first, int last, int gap) {
    int i, j, key;
    for (i = first + gap; i <= last; i += gap) {
        key = list[i];
        for (j = i - gap; j >= first && list[j] < key; j -= gap) {
            list[j + gap] = list[j];
        }
        list[j + gap] = key;
    }
}
 
void shellSort(int list[], int n) {
    int gap;
    for (gap = n / 2; gap > 0; gap /= 2) {
        if (gap % 2 == 0) {
            gap++;
        }
        for (int i = 0; i < gap; i++) {
            sortGapInsertion(list, i, n - 1, gap);
        }
    }
}
    
 
int main() {
    int N, M;
    const int SIZE = 100000;
    int list[SIZE];
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
    
    /*셸 정렬 - 내림차순으로 구현*/
    shellSort(list, N);
 
    /*투 포인터*/
    int left = 0;
    int right = 0;
    int ans = 2000000000;
    while (right<N&&left<N) {
        int temp = list[left] - list[right];
        if (temp > M) {
            ans = min(ans, temp);
            left++;
        }
        else if (temp < M) {
            right++;
        }
        else if (temp == M) {
            ans = min(ans, temp);
            right++;
        }
    }
 
    cout << ans;
    return 0;
}