백준 17298 : 오큰수

문제 설명

---

수열의 각 원소에 대해 오른쪽에 있는 더 큰 수 중 가장 왼쪽에 있는 수를 오큰수라고 한다. 이때 주어진 모든 배열의 수의 오큰수를 출력한다. 해당하는 값이 없으면 -1을 출력한다. 

---

 

이 문제는 스택을 이용해서 풀면 된다. 주어진 배열을 순차적으로 스택에 넣어가며, 스택에 있는 값보다 현재 탐색한 값이 더 크다면, 스택에서 해당 수를 빼내고 그값의 오큰수는 현재 탐색중인 값으로 한다. 해당 방법을 이용하여 주어진 배열을 순차 탐색해나가면 된다.

 

• 반복문을 통해 각 원소 x(현재 탐색중인 배열의 값)를 입력받는다.
• 스택이 비어있다면 스택에 (현재 인덱스, 배열의 값) 쌍을 추가.
• 스택이 비어있지 않은 경우, 스택의 최상단 원소를 검사하여 x가 더 크면 스택에서 꺼내고, 그 인덱스의 오큰수를 x로 설정한다.
• x가 스택의 최상단 원소보다 작거나 같으면 현재 원소를 스택에 추가한다.

---

소스 코드

#include <stdio.h>
#include <stack>

using namespace std;

int n;
int ans[1000010];
stack <pair<int, int>> st;

int main()
{
    int i;
    scanf("%d", &n);
    for(i=0;i<n;i++) {
        int x;
        scanf("%d", &x);
        if(st.empty()) st.push({i, x});
        else {
            while(!st.empty()) {
                int t = st.top().second;
                if(t < x) {
                    int idx = st.top().first;
                    ans[idx] = x;
                    st.pop();
                }
                else {
                    break;
                }
            }
            st.push({i, x});
        }
    }
    while(!st.empty()) {
        int idx = st.top().first;
        ans[idx] = -1;
        st.pop();
    }
    for(i=0;i<n;i++) printf("%d ", ans[i]);
    return 0;
}