BOJ - 2493번 탑(C++)

문제 출처 : https://www.acmicpc.net/problem/2493

문제 난이도

Gold 5

문제 접근법

for문 돌리면 시간초과 나는 문제다.
탑이 수신 받는 걸 잘 살피다 보면 stack을 써도 된다는 걸 찾을 수 있다.
stack 맨 위에 넣은 높은 탑이 오른쪽 탑보다 크면 오른쪽 탑의 값을 갱신해준다. (왼쪽 방향으로 레이저를 쏜다고 했으니깐 가능)

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>


using namespace std;

int top[500001];
int raser[500001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	stack<pair<int, int>> s;
	for (int i = 1; i <= N; i++) {
		cin >> top[i];
	}
	s.push({ top[1], 1 });
	for (int i = 2; i <=N; i++) {
		while (!s.empty()) {
			if (s.top().first > top[i]) {
				raser[i] = s.top().second;
				break;
			}
			s.pop();
		}
		s.push({ top[i],i });
	}

	for (int i = 1; i <= N; i++) {
		cout << raser[i] << " ";
	}
	
	return 0;
}

피드백

사실 이 문제도 걍 생각없이 for문으로 풀었다가 역시나 4초대에서 시간초과가 나서 다른 사람 풀이를 찾아봤다. 스택이래서 놀람.. 생각지도 못한 알고리즘이라 응용력의 한계를 깨달았다.
그리고 푸는데 그냥 if문으로 크고 작고 push pop을 하는게 아니라 s.empty()까지 pop을 해줘야하는 걸 알았는데 그 담에 어떻게 값을 넣어줘야하는지 고민했다.
근데 허무할 정도로 쉬웠다. 어떻게 하면 이런 문제는 아무것도 참고 안하고 푸는 수준이 될까 더 정진허자