1138번 한 줄로 서기

https://www.acmicpc.net/problem/1138

코드 2개 첨부

첫 번째 코드 :

제일 큰 사람인 N은 무조건 0이므로, 20번 째 줄에서 오류가 발생하지 않는다.

또한, 큰 사람부터 하는 이유는 '왼쪽에서 나보다 큰 사람의 수'가 같을 때에도(=arr[i] 같을 때)

고려해줘야 하는데, 이 때, insert를 하게된다면, 나중에 insert한 값이 왼쪽으로 들어가게 된다.

오른쪽으로 들어가게 되면, 키가 더 작은 사람의 arr[i] 값에 따른 위치가 다르게 된다.

예시)

4

2 1 1 0

일 때,

키가 2인 사람의 arr[i] = 1

키가 3인 사람의 arr[i] = 1이므로, arr[i]는 같다.

이 때, 큰 사람부터 해야된다.

즉, 

v.insert(v.begin() + arr[i], 3);

v.insert(v.begin() + arr[i], 2);

이렇게 해야 2, 3의 순서로 들어가게 된다.

v.insert(v.begin() + arr[i], 2);

v.insert(v.begin() + arr[i], 3);

으로 하게 된다면, 3, 2가 되고, 2에 따른 arr[i]의 값에 따른 위치와 다르게 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n, arr[11];
vector<int> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
 
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = n; i >= 1; i--) {
        v.insert(v.begin() + arr[i], i);
    }
 
    for (auto i : v) {
        printf("%d ", i);
    }
 
    printf("\n");
 
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
vector<pair<int, int> > v, ans;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
 
    scanf("%d", &n);
 
    int input;
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &input);
        v.push_back({ input, i });
    }
 
    sort(v.begin(), v.end());
 
 
    for (auto i : v) {
        if (i.first == 0) {
            ans.push_back(i);
            continue;
        }
 
        int order = 0, cnt = 0;
 
        for (int j = 0; j < ans.size(); j++) {
            ++order;
            if (i.second < ans[j].second) {
                if (++cnt == i.first) {
                    for (int k = j; k < ans.size(); k++) {
                        if (i.first == ans[k].first) {
                            ++order;
                        }
                    }
                    break;
                }
            }
        }
 
        ans.insert(ans.begin() + order, i);
    }
 
    for (auto i : ans) {
        printf("%d ", i.second);
    }
 
    printf("\n");
 
    return 0;
}