[BOJ/백준][Gold5] 2493 : 탑 (C++)

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

2493번: 탑

 

 

[난이도] Gold5
[유형] Stack

[풀이]
i:0~N-1 탑을 순회하면서 스택을 이용해 문제를 해결한다
1) stack이 비어있으면 왼쪽에 레이저를 가리는 탑이 없는 것으로 ans[i]=-1로 기록한다. (-1로 기록하는 이유는 마지막에 +1씩 해줄 것이기 때문에)

2) stack에 값이 있으면 i번 탑보다 큰 탑이 나오거나 stack이 빌 때까지 stack의 index들을 pop 해준다.
(이 탑들은 어차피 더 오른쪽에 있는 탑들에게는 i번 탑에 가려서 안보이므로 필요가 없다.)
case1) pop을 하다 stack이 빈 경우 : -1을 기록
case2) pop을 하다 큰 탑을 만난 경우 : 그 탑의 index를 push.

3) stack에 현재 index i를 push한다.

위의 과정을 반복하면 모든 index에 대해 답을 구할 수 있다.

 

#include <cstdio>
#include <stack>
using namespace std;
int N,a[500000],ans[500000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    stack<int> st;
    for(int i=0;i<N;i++){   
        while(!st.empty() && a[st.top()]<=a[i]) st.pop();     
        if(st.empty()) ans[i]=-1;
        else ans[i] = st.top();
        st.push(i);
    }
    for(int i=0;i<N;i++) printf("%d ",ans[i]+1);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2493.cpp