[백준OJ] 17298번 오큰수

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

17298번: 오큰수

---

 

풀이

스택을 이용해서 문제를 해결할것이다. 오른쪽에 있는 수중에 자신보다 큰 가장 왼쪽에 있는수를 구해주어야 하므로, 오른쪽에서 왼쪽으로 탐색을 할것이다.

 

2번 입출력 예시를 가지고 설명을 해보겠다.

4
3 5 2 7

먼저 7의 오른쪽엔 아무것도 없기때문에 ,4번째 Result는 -1이 되고, 스택에 자신의 수를 쌓는다. 여기서 스택은 자신의 오른쪽에 있는 수들이라 생각을 하자.

현재 상황

 

 

그다음 수를 보자. 2를 기준으로  오른쪽에 있는 수들중 가장 왼쪽에 있는 수는, stack에 가장 최근 들어간 숫자가 된다.(Stack.top()). 따라서 2의 오른쪽에서 가장 왼쪽에 있는 수는 7이 된다. 2보다 7이 더 크므로, 3번째 Result는 7이 되고, 스택에 자신의 수를 쌓는다.

현재 상황

 

그다음 수를 보자. 5를 기준으로 오른쪽에 있는 수들은 순서대로 2와 7이 된다. 이중 5보다 크면서, 가장 왼쪽에있는 수를 구해야하므로, 스택의 탑을 보면된다. 스택의 top이 2인데, 5보다 작으므로, pop시켜준다. pop을 시켜주면 스택의top은 7이 되므로, 5의 오른쪽 수들중, 5보다 크면서 가장 왼쪽에 있는 수는 7이 된다고 할 수 있으므로, 2번째 Result는 7이 되고, 스택에 자신의 수를 쌓으면된다.

 

마지막수를 보자. 3을 기준으로 오른쪽에 있는 수를 모아둔 stack을 보면 5와 7이 있다. 이때 스택의 top에있는 원소가 가장 왼쪽에 있는 수이므로 3과 5를 비교해봤을때 3<5 이므로, 1번째 Result는 5가 되고, 스택에 자신의 수를 쌓는다.

 

 

정리를 하자면.

1. 오른쪽부터 차례대로 탐색한다.

2-1. 만약 stack이 비어있다면, 해당 result에 -1을 대입한뒤 stack에 자신의 수를 push한다.

2-2. 2-1이 아니라면, stack의 top과 비교를 한다.

2-2-1. 만약 현재 수가 stack의 top보다 작다면, 해당 result에 stack의 top을 대입한뒤, stack에 자신의 수를 push한다.

2-2-2. 2-2-1이 아니라면, stack이 비거나, stack의 top이 자기 자신보다 커질때까지 pop해준다. 그다음 stack이 비어있다면 -1을, 아니면 stack의 top을 result에 대입한뒤, 자신의 수를 stack에 push한다.

 

 

반응형

 

코드

#include <iostream>
#include<algorithm>
#include<stack>

using namespace std;

int maze[1000000];
int ret[1000000];

int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>maze[i];
    }
    
    stack<int> st;
    for(int i=n-1;i>=0;i--){
        if(st.empty()){
            st.push(maze[i]);
            ret[i]=-1;
        }
        else{
            if(st.top()>maze[i]){
                ret[i]=st.top();
                st.push(maze[i]);
            }
            else{
                while(!st.empty()&&st.top()<=maze[i]){
                    st.pop();
                }
                if(st.empty()){
                    ret[i]=-1;
                    st.push(maze[i]);
                }
                else{
                    ret[i]=st.top();
                    st.push(maze[i]);
                }
            }
        }
    }
    
    for(int i=0;i<n;i++){
        cout<<ret[i]<<" ";
    }
	return 0;
}