백준 1138번 한 줄로 서기 C++

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

1138번: 한 줄로 서기

 

처음에 작은순서대로 정렬되어있기때문에 앞에서부터 배치하면 후에 배치할 숫자는 무조건 지금 숫자보다 크고 이미 배치되어있는 숫자는 지금 숫자보다 작다. 

그렇기 때문에 처음 인덱스부터 자기보다 큰 사람의 수 + 지금까지 배치된 사람 수 만큼 이동해서 현재 숫자를 배치하면 된다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;
vector<int> v;
vector<int> ans;

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

    cin >> n;
    v = vector<int>(n);
    ans = vector<int>(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        int targetCnt = v[i];
        for (int j = 0; j < n; j++) {
            if (cnt == targetCnt) {
                if (ans[j] != 0) continue;
                ans[j] = i + 1;
                break;
            }
            if (ans[j] == 0) cnt++;
        }
    }
    for (auto a : ans) {
        cout << a << " ";
    }
}