문제

BOJ 2493, 탑

핵심

• 입력의 크기가 $500'000$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 스택의 성질을 이용해서 효율성을 확 올려야 한다. 해당 문제가 스택으로 푸는지 아닌지도 알기 힘들겠지만, 일반적으로 입력을 받으면서 바로 처리하는 구조로 만들 수 있으면 스택의 성질을 이용하기가 수월하다.
• 더미 노드를 만들면 구현이 훨씬 쉬워진다. 더미는 스택에서 뽑아낼 수 없는 데이터로 해당 탑보다 높은 탑이 없다면 0을 가리키게 구현하였다.

개선

• 입력을 다 받고나서 스택으로 처리하는 $O(N^2)$ 코드이다. 입력을 받으면서 바로 처리할 수 없을까? 스택을 효율적으로 사용할 수 없을까? 고민해보자.

#include <iostream>
#include <stack>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	stack<pair<int, int>> s;
	for (int i = 1; i <= n; ++i) {
		int num;
		cin >> num;
		s.push({num, i});
	}
	stack<int> ans;
	while (!s.empty()) {
		auto cur = s.top();
		s.pop();
		stack<pair<int, int>> tmp;
		while (!s.empty()) {
			auto right = s.top(); s.pop();
			tmp.push(right);
			if (right.first >= cur.first) {
				ans.push(right.second);
				break; 
			}
		}
		if (s.empty())
			ans.push(0);
		while (!tmp.empty()) {
			auto cur = tmp.top(); tmp.pop();
			s.push(cur);
		}
	}
	while (!ans.empty()) {
		cout << ans.top() << ' ';
		ans.pop();
	}
}

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
#include <stack>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	stack<pair<int, int>> s;
	pair<int, int> dummy = {0x7fffffff, 0};
	s.push(dummy);
	for (int i = 1; i <= n; ++i) {
		int h;
		cin >> h;
		while (s.top().first < h)
			s.pop();
		cout << s.top().second << ' ';
		s.push({h, i});
	}
}

Java

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        Stack<int[]> s = new Stack<>();
        s.push(new int[]{Integer.MAX_VALUE, 0});
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int h = Integer.parseInt(st.nextToken());
            while (s.peek()[0] < h)
                s.pop();
            bw.write(s.peek()[1] + " ");
            s.push(new int[]{h, i});
        }
        bw.flush();
        bw.close();
        br.close();
    }
}