[백준 1138번] 한 줄로 서기 풀이

#백준 #백준 1138번 #백준 한줄로 서기 #CPP

1138번: 한 줄로 서기

 

N명의 사람에 대하여 키가 1, 2, ..., N인 사람의 왼쪽에 자신보다 더 큰 사람이 몇명 있는지 주어진다. 

문제에서 제시된 케이스를 살펴보면,

 

4
2 1 1 0

 

1번 앞에는 1번 보다 큰 사람 2명이, 2번 앞에는 2번 보다 큰 사람 1명이, 3번 앞에는 3번 보다 큰 사람 1명이 있다는 뜻이다. 

 

먼저, 가장 큰 사람인 4번을 벡터에 넣어보면 원소가 4 하나인 벡터가 된다.

 

이후 N-1번째 사람 부터 1번 사람까지 벡터의 어느 위치에 배열 되어야 하는지 찾는다. 위의 예시에서 3번 사람의 경우 앞에 3번 보다 큰 사람 1명이 있다고 하였다. 3보다 큰 수는 4 밖에 없기 때문에 3은 자연스럽게 4의 뒤, 1번 위치에 들어가야 한다. 3번을 인덱스 1번에 삽입해주도록 하자.

 

 

다음으로 2번 사람을 벡터에 적절히 넣어주자. 2번 앞에는 2번 보다 큰 사람이 1명 있다고 하였고, 아래의 0번, 1번, 2번 중 1번에 2가 삽입 되어야 2번 보다 큰 사람은 4 한명 뿐이게 된다. 2번 사람을 인덱스 1번에 삽입해주도록 하자.

 

 

마지막으로, 1번 사람을 적절히 넣어주자. 1번 앞에는 1번 보다 큰 사람이 2명 있다고 하였다. 따라서 아래의 0번, 1번, 2번 중 2번에 삽입되어야 1번 보다 큰 사람이 2명이게 된다. (다들 눈치챘겠지만, ) i번째 사람의 삽입 위치는 i번째 사람 앞에 있는 큰 사람의 수이다. 

 

 

이렇게 N번 사람 부터 1번 사람까지 적절히 삽입해주면, 최종적으로 답의 배열이 도출된다.

 

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
using namespace std;

int main() {

    int N;
    scanf("%d", &N);

    vector<int> v(N+1);
    for (int i=1; i<=N; i++)
        scanf("%d", &v[i]);

    vector<int> vRe;
    vRe.push_back(N);

    for (int i=N-1; i>=1; i--)
        vRe.insert(vRe.begin()+v[i], i);

    for (int i=0; i<vRe.size(); i++)
        printf("%d ", vRe[i]);
    return 0;
}