[정렬] 백준 2230 :: 수 고르기

수 고르기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1319	386	283	28.442%

문제

N(1≤N≤100,000)개의 수로 이루어진 수열 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(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다.

출력

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

예제 입력 1 

3 3
1
5
3

예제 출력 1 

4

 

 문제 풀이

1차 풀이 (  2256 KB,  24 ms)

• 오름차순으로 정렬.
• upper_bound()를 사용해서 M-1보다 큰, 첫번째 요소의 위치를 얻어옴.
• 각 i마다 계산해서 최솟값 갱신.

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

using int32 = int32_t;
using int64 = int64_t;


int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        int32 N, M, min_val = 2'000'000'001;
        cin >> N >> M;
        int32 A[N];
        for(int32 i=0; i<N; i++) cin >> A[i];
        sort(A, A+N);

        for(int32 i=0; i<N-1; i++){
                auto ptr = upper_bound(A+i, A+N, A[i] + M -1);
                if(ptr == A+N) continue;
                auto val = *ptr - A[i];
                if(M <= val && val < min_val) min_val = val;
                if(M == min_val) break;
        }
        cout << min_val;
}

2차 풀이 (  2256 KB,  20 ms)

• 오름차순으로 정렬.
• 왼쪽 커서와, 오른쪽 커서를 만들고,
  두 커서 값의 차이에 따라,  커서의 위치를 변경.
• 왼쪽 커서를 증가시키면,  차이는 감소하고,
  오른쪽 커서를 증가시키면, 차이는 증가한다.
• 두 커서의 값의 차이를 구할때 마다, 최솟값 갱신.

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

using int32 = int32_t;
using int64 = int64_t;


int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        int32 N, M, min_diff = 2'000'000'001;
        cin >> N >> M;
        int32 A[N];
        for(int32 i=0; i<N; i++) cin >> A[i];
        sort(A, A+N);

        int32 l = 0;
        int32 r = 0;
        int32 diff = 0;
        while(r != N){
                diff = A[r] - A[l];
                if(M <= diff){
                        l++;
                        if(diff < min_diff) min_diff = diff;
                }
                else r++;
        }
        cout << min_diff;
}

3차 풀이 (  4304 KB,  12 ms)

• 저수준 입출력 사용.

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

using int32 = int32_t;
using int64 = int64_t;

const int BUF_SIZE = 1 << 20;        // 메모리 초과 가능, 적당히 조절할 것.
char input_buf[BUF_SIZE], output_buf[BUF_SIZE];
int input_buf_pos, output_buf_pos;
enum io_mode {READ, WRITE};
inline void char_io(io_mode mode, char &target)
{
        if(mode == READ) {
                if (input_buf_pos == BUF_SIZE)
                {
                        fread(input_buf, sizeof(char), BUF_SIZE, stdin);
                        input_buf_pos = 0;
                }
                target = input_buf[input_buf_pos++];
        }
        else {
                if(output_buf_pos == BUF_SIZE || target == EOF)
                {
                        fwrite(output_buf, sizeof(char), output_buf_pos, stdout);
                        output_buf_pos = 0;
                }
                output_buf[output_buf_pos++] = target;
        }
}
inline void char_io(io_mode mode, char &&target){
        char_io(mode, target);
}
inline void int_io(io_mode mode, int &target)
{
        char c;
        if(mode == READ){
                bool negative = false;
                int ret = 0;
                while(true)
                {
                        char_io(READ, c);
                        if(c == '\n' || c == ' ') break;
                        if(c == '-') {
                                negative = true;
                                continue;
                        }
                        ret = ret * 10 + (c & 0b1111);
                }
                target = negative ? -ret : ret;
        }
        else {
                int abs = target;
                int div = 1'000'000'000;
                char quotient = 0;
                if(abs < 0) {
                        char_io(WRITE, '-');
                        abs *= -1;
                }
                while(abs < div && div != 1) { div /= 10; }
                while(div != 0){
                        quotient = '0' + (char)((abs / div)%10);
                        char_io(WRITE, quotient);
                        div /= 10;
                }
        }
}
inline void int_io(io_mode mode, int &&target){
        int_io(mode, target);
}

int main() {

        int32 N, M, min_diff = 2'000'000'001;
        int_io(READ, N);
        int_io(READ, M);
        int32 A[N];
        for(int32 i=0; i<N; i++) int_io(READ, A[i]);
        sort(A, A+N);

        int32 l = 0;
        int32 r = 0;
        int32 diff = 0;
        while(r != N){
                diff = A[r] - A[l];
                if(M <= diff){
                        l++;
                        if(diff < min_diff) min_diff = diff;
                }
                else r++;
        }
        int_io(WRITE, min_diff);
        char_io(WRITE, EOF);
}