BOJ 1138번 한 줄로 서기 [그리디 알고리즘]

문제 이해

처음 입력이 4라면
그 다음줄에 주어지는 입력은 키 1부터 4까지 자기 왼쪽에 자기보다 키큰사람 수를 입력한다
이 정보로 이 사람들이 어떤 순서로 서있는지 맞추는 문제다.

탐욕적 선택

리스트에 키가 제일 큰 사람부터 넣는다. 입력받은 값을 인덱스로 넣는다.
2 1 1 0 을 예로 들자면 4가 제일 크니까 4번째 값인 0을 인덱스로 리스트에 들어간다.
3번째는 1번째 인덱스에 들어간다. 그 다음 2도 1번째 인덱스에 들어가야하기때문에 3을 옆으로 밀고 그자리를 차지한다.
마지막 1은 2를 인덱스로 들어가야 하기 때문에 또 3을 밀고 그 자리에 들어간다
4 2 1 3 이 된다.

증명

좀 생각을 해봤는데 음.. 최적해라는 개념이 이 문제엔 없지 않나 싶다.
무슨말이냐면 위의 순서 4 2 1 3이 나오기 위해선 2 1 1 0 밖에 없지 않나..?
따라서 내가 생각한 선택들로 이루어진 답 외에 다른 선택들로 이루어진 답이 있다고 해도
어차피 그 역시 4 2 1 3 아닌가....??
따라서 '다른 선택으로 이루어진 답'을 '내가 생각한 선택'으로 대체한다해도
내가 생각한 논리는 현시점에서 이미 맞기때문에 증명에 의의가 없다.
굳이 증명을 해보자면 다른 방법으로 선택해서 나열된수가 답이라면 여기에 첫번째 선택한 수부터를
내가 생각한대로 입력받은 값을 인덱스로 집어넣었을때 역시 완벽하게 되기 때문에 이 선택은 탐욕적 선택임을 증명 가능하다.

계획 세우기

1. 입력할 갯수를 입력받는다.
2. 스택에 입력받은 값을 차곡 차곡 쌓는다.
3. 스택의 맨위의값을 인덱스로 하여 현재스택의 크기를 벡터에 넣는다.
4. 스택이 빌 때 까지 반복한다.
5. 벡터를 처음부터 순회하며 출력한다.

code

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main(){
    int n, x;
    stack <int> stk;
    vector <int> answer;
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        cin >> x;
        stk.push(x);
    }
    while(!stk.empty()){
        answer.insert(answer.begin() + stk.top(), stk.size());
        stk.pop();
    }
    for(int i = 0 ; i < n ; i++){
        cout << answer[i] << " ";
    }
    cout << endl;

    return 0;
}