[BOJ] 백준 2605 줄 세우기

[BOJ] 백준 2605 줄 세우기

문제 링크 : https://www.acmicpc.net/problem/2605




이 문제를 처음 접근할 때, 문자열 처리로 해결하려고 하였습니다. 문자열 처리로 풀 경우 string.insert() 함수를 사용하면 되는데, 경우의 수를 세기 힘들었습니다.


스택을 사용하면 입력받은 순위대로 pop을 하고, 현재 줄을 서는 숫자를 push, 그리고 pop한 숫자를 다시 push 해주면 됩니다.

소스 코드 :

#include 
#include 
using namespace std;

int main() {
 int N;
 cin >> N; cin.ignore();
 stack st;
 for (int i = 0; i < N; i++) {
  int t = 0;
  cin >> t; cin.ignore();
  stack temp;

  // 번호(0~t) 까지 임시스택 temp에 저장 후 pop.
  for (int j = 0; j < t; j++) {
   if (!st.empty()) {
    temp.push(st.top());
    st.pop();
   }
  }
  
  // 현재 학생 번호를 스택에 push.
  st.push(i + 1);

  // 임시스택에 저장해 둔 학생들을 다시 스택에 저장.
  for (int j = 0; j < t; j++) {
   if (!temp.empty()) {
    st.push(temp.top());
    temp.pop();
   }
  }
 }

 // 입력 순서대로 출력하기 위해 스택의 성질을 이용하여 역전.
 stack p;
 for (int i = 0; i < N; i++) {
  p.push(st.top());
  st.pop();
 }
 for (int i = 0; i < N; i++) {
  cout << p.top() << ' ';
  p.pop();
 }

}