[2605번] 줄 세우기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Stack 이용

이 문제에서 스택을 이용해야 된다는 생각을 잡아낼 수 있는부분은 1이 계속 뒤로 밀려나는 과정에서 알 수 있다. (LIFO 형식)

그림을 통해 문제의 예제 입력에 따른 예제 출력의 과정을 확인해보도록 하자.

마지막 스택 뒤집기는 s에 있는 값을 tmp로 옮기고 tmp를 출력하면 s가 거꾸로 쌓이게 된다.

소스 코드 : 

#include <iostream>
#include <stack>
 
using namespace std;
 
int main()
{
    int n;
    int arr[101];
    stack<int> s;
    stack<int> tmp;
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    
        for (int j = 0; j < arr[i]; j++)
        {
            tmp.push(s.top());
            s.pop();
        }
 
        s.push(i+1);
 
        for (int j = 0; j < arr[i]; j++)
        {
            s.push(tmp.top());
            tmp.pop();
        }
    }
 
    // 스택 뒤집기
    while (!s.empty())
    {
        tmp.push(s.top());
        s.pop();
    }
 
    // 출력
    while (!tmp.empty())
    {
        printf("%d ", tmp.top());
        tmp.pop();
    }
 
    return 0;
}