문제 출처

1. 문제설명

• N개의 탑 K가 주어진다.
  • 1<=N<=500,000
  • 1<=K<=100,000,000
• 입력 예시
  • N=5, K={6,9,5,7,4}
  • 마지막 index인 4보다 큰 왼쪽 값이 7이므로 7에 해당하는 index 4
  • 7보다 큰 왼쪽 값은 9이므로, 건너뛴 5와 7은 9에 해당하는 index 2
  • 9보다 큰 왼쪽 값은 없으므로, 0
  • 6보다 큰 왼쪽 값은 없으므로, 0
  • 출력 : {0,0,2,2,4}

2. 알고리즘 설계

• 입력 예시 시뮬레이션
  • K=6
    • print(“0”)
    • stack {6}
  • K=9
    • stack {} // 6 pop
    • print(“0”)
    • stack {9}
  • K=5
    • print(“2”) // 9>5, 9의 index
    • stack {5,9}
  • K=7
    • stack {9} // 5<7, 5 pop
    • print(“2”) // 9>7, 9의 index
    • stack {7,9}
  • K=4
    • print(4) // 7>4, 7의 index
    • stack {4,7,9}

3. 로직

• LIFO 구조인 stack을 사용해 구현
• K를 입력 받을 때마다
  • 스택이 비지 않았다면?
    • 현재 스택의 값이 K보다 클 때까지 pop
    • K보다 큰 값을 만나면 해당 인덱스 출력
  • 스택이 비었다면?
    • 0 출력
  • K, K의 index stack에 삽입

4. 전체 코드

#include <stack>
#include <iostream>
using namespace std;
typedef struct { int n, idx; }pos;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	stack<pos> st;
	
	int N; cin >> N;
	for (int k, i = 1; i <= N; i++) {
		cin >> k;

		while (!st.empty()) {
			pos cur = st.top();
			if (cur.n > k) {
				cout << cur.idx << " ";
				break;
			}
			st.pop();
		}

		if (st.empty()) cout << "0 ";
		st.push({ k, i });
	}

	return 0;
}

5. 소감

• 처음에 stack을 두개 사용해서 구현하려고 했었다.
  • 입력값 저장한 stack
  • 입력값보다 크면 stack에 넣고, 아니면 버림
• 위와 같이 구현할 경우, 배열 크기가 커지면 속도가 매우 오래 걸린다.
  • 시간 초과를 받았었다.
• 위의 코드는 여러 블로그를 참조한 결과인데,
  • 솔직히 stack 하나로 구현하는 건 생각조차 하지 못했다.
• 역시 알고리즘은 꾸준히 오랫동안 많은 문제를 경험하는 게 중요한 것 같다.