백준 g5 2493 탑 c++

https://www.acmicpc.net/problem/2493

​

풀이

역순으로 맨 뒤에서부터 시작 <- cur

stack의 top과 cur을 비교해서 cur이 더 크면, top은 cur로 신호가 간다

그렇지 않으면, cur의 신호 역시 stack에 쌓이고 다음으로 넘어간다

​

예시)

6 9 5 7 4 이렇게 있을 때, 4부터 시작

• 4와 7 비교, 7이 더 크므로 4의 신호는 7로 간다 / 4 pop
  • 7 push
• 7(스택의 top) 과 5 비교, 5가 더 작으므로 7의 신호는 그 다음으로 넘어간다
  • 5 push
• 5(top) 과 9 비교, 9가 더 크므로 5는 9로 간다 / 5 pop
• 다음 top인 7과 9 비교, 9가 더 크므로 7은 9로 간다 / 7 pop
  • 9 push

...

​

고려했던 것

• 수도코드랑 다르게 실제로는 stack에 쌓여있는 값들의 index도 필요했기에 stack<pair<int, int>>로 선언
• 2년 전에 풀었던 풀이는 역순이 아닌 정방향으로 풀이, 생각해보면 굳이 역순으로 풀 필요는 없음
  • 그렇지만 문제가 복잡해질수록 특히 시뮬레이션 같은 경우는 괜히 다르게 풀었다가 틀리는 경우가 많으므로 웬만하면 문제 그대로 따라가는 게 나음

/*boj g5 2493 탑*/
#include <iostream>
#include <stack>
#define MAXN 500005
using namespace std;

int N;
int tower[MAXN];
int answer[MAXN];
stack<pair<int, int>> S; // index, height
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> tower[i];
    }

    for (int i = N; i >= 1; i--)
    {
        int cur = tower[i];

        while (!S.empty() && S.top().second < cur)
        {
            answer[S.top().first] = i;
            S.pop();
        }

        S.push({i, cur});
    }

    for (int i = 1; i <= N; i++)
    {
        cout << answer[i] << " ";
    }
    cout << "\n";
}

 

2년 전에 풀었던 풀이

정방향으로 풂, 높았던 탑들을 stack에 쌓아가며 푸는 방식

초기값으로 max_height를 넣고 시작

​

예시) 6 9 5 7 4

{max_height, 6}

{max_height, 9} 6보다 9가 더 크므로 6 삭제, 뒤에 오는 탑들은 9로 신호가 간다 9가 제일 크니까

{max_height, 9, 5}

{max_height, 9, 7} 5보다 7이 더 크므로 5 삭제, 뒤에 오는 탑들은 7로 신호가 간다

...

 

/*g5 2493 탑*/

#include <bits/stdc++.h>
using namespace std;

stack<pair<int, int>> tower;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	stack <pair<int,int>> tower;
	tower.push({ 100000001, 0 });
	
	for (int i = 1; i <= n; i++) {
		int num;
		cin >> num;

		while (tower.top().first < num) {
			tower.pop();
		}
		cout << tower.top().second << " ";
		tower.push({ num, i });
	}
}