16043 : Missing Gnomes

풀이

주어지지 않은 숫자 중 작은 숫자부터 그리디하게 채워넣으면 된다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, c[100001];
vector<int> a, b, r;

int main() {
    scanf("%d %d", &n, &m);
    a.resize(m+1);
    for (int i = 0, x; i < m; i++) {
        scanf("%d", &a[i]);
        c[a[i]] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (!c[i]) b.push_back(i);
    }

    int i = 0, j = 0;
    for (; i < m; i++) {
        for (; j < n-m; j++) {
            if (a[i] < b[j]) break;
            r.push_back(b[j]);
        }
        r.push_back(a[i]);
    }
    for (; j < n-m; j++) {
        r.push_back(b[j]);
    }

    for (int it : r) {
        printf("%d\n", it);
    }

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-06 16:34

Read more posts by this author