[BOJ] 백준 2493 탑

[BOJ] 백준 2493 탑

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


이 문제는 스택 자료구조를 사용하면 빠르게 풀 수 있습니다.
스택을 사용하지 않고 문자열로 접근을 하면 시간초과 에러가 발생할 가능성이 있습니다.


저는 2개의 스택을 사용하였고, 자신보다 큰 탑이 나올때 까지 pop 을 하면 되는 문제 입니다.

소스코드 :

#include 
#include 
using namespace std;


int main() {
 int t;
 cin >> t;
 cin.ignore();

 // 현재 검사해야 되는 탑보다 높이가 높은 탑을 관리하기 위한 스택 st 선언.
 stack st;
 
 // st 안의 탑의 index를 관리하기 위한 스택 idx 선언.
 stack idx;

 // 수신하는 탑의 index를 관리하기 위한 arr 동적 메모리 할당.
 int *arr = new int[t];

 // arr의 인덱스를 하나씩 올리기 위한 cnt 변수 선언.
 int cnt = 0;

 for (int i = 0; i < t; i++) {
  int a;
  cin >> a;
  cnt++;

  // st가 비어있다면, 입력받은 탑을 스택에 넣는다.
  if (st.empty()) {
   st.push(a);
   idx.push(cnt);
   // 스택이 비어있다면, 입력받은 탑보다 큰 탑은 없으므로 0 대입.
   arr[i] = 0;
  }
  else {
   // 입력받은 탑(a)보다 큰 탑이 나올때까지 pop.
   while (st.top() < a) {
    st.pop();
    idx.pop();
    if (st.empty()) break;
   }
   // pop 반복 실시 후 스택이 비어있다면, 입력받은 탑보다 큰 탑은 없으므로 0 대입.
   if (st.empty()) {
    arr[i] = 0;
    st.push(a);
    idx.push(cnt);
    continue;
   }
   
   // 현재 탑의 전파를 수신하는 탑은 남아있는 탑의 번호임. 
   arr[i] = idx.top();
   // 현재 탑을 스택에 넣음.
   st.push(a);
   idx.push(cnt);

  }

 }
 for (int i = 0; i < t; i++) {
  cout << arr[i] << ' ';
 }
}