[Stack 활용] 17298. 오큰수

 

17298번: 오큰수

---

요약

1. 크기가 N인 배열에서  

2. i번째 인덱스의 배열의 값에서 오른쪽에 있는 수 중 가장 큰 수를 출력

3. 만약 오른쪽에 있는 수가 현재 인덱스의 배열의 값보다 작다면 -1 출력

 

이중 포문으로 해결은 가능하지만 최악의 경우에 1,000,000 * 1,000,000 = 1,000,000,000,000 (1조) 즉, 1조 / 1억(1s) = 10,000s가 걸리게 되어 시간초과가 발생합니다.

 

문제는 배열의 i번째 값에서 오른쪽에 있는 수 중 가장 큰 수를 어떻게 빠르게 구하냐가 관건입니다.

 

아이디어가 떠오르지 않아 검색을 해보았는데 대부분 스택을 이용하여 배열을 한번만 훑어 O(N) 시간 안에 해결하였습니다.

 

---

Solution : Stack 활용하기

배열 끝 값부터 0번째 인덱스 값까지 검사하여 출력 배열의 값을 도출합니다. 이 때 스택을 이용해서 검사하는데, 스택을 어떻게 활용하였는지 그림을 통해 살펴봅시다.

 

v는 입력받은 배열입니다. ans는 구할 오큰수 배열 

set

1) 오큰수 배열의 마지막 값은 비교할 대상이 없기 때문에 반드시 -1값이 들어갑니다.

2) stack에 현재 인덱스 배열값을 push합니다.

 

ans : ( ) ( ) ( ) -1

 

이제부터 스택을 이용하여 끝에서부터 하나씩 오큰수 배열을 채워보겠습니다.

1. 우선 stack의 top에 있는 값과 현재 인덱스 값을 비교합니다.

 

• 여기서 스택의 top에 있는 값이 더 작거나 같은 경우 스택의 top에 있는 값이 더 클 때까지 스택을 pop 합니다.

 

2. 비로소 스택의 탑 값이 더 커지게 되면 바로 그 스택의 탑에 있는 값이 오큰수 값이 되므로, 정답 배열에 값을 넣어줍니다.

 

3. 여기서 끝이 아니라 현재 인덱스의 값을 stack에 푸쉬해주어야 합니다.

why : 현재 값이 다음 진행하는 인덱스의 값의 오큰수가 될 수 있기 때문에 현재 인덱스의 값을 stack에 푸쉬합니다

 

주의해야 할 점 !

이 때 오른쪽에 있는 값이 모두 현재 인덱스값보다 작은 경우 스택이 비워지는데 이 경우에는 스택에 현재 인덱스 값을 스택에 넣고, 정답 배열에 -1을 넣어줍니다.

 

ans : ( ) ( ) (7) -1

 

이 매커니즘으로 다음 오큰수를 구해봅시다.

 

1. 현재 stack에는 이전 과정을 통해 2, 7이 들어가 있습니다.

 

2. 현재 인덱스 값인 5와 stack의 top ( 2 )를 비교하면 현재 인덱스 값이 더 크니 더 작을때까지 stack을 pop합니다.

 

3. 비로소 stack의 탑 값이 더 커지게 되면 정답 배열 값은 스택의 탑 값이 되고, 스택에 현재 인덱스 값인 5가 push 됩니다.

 

ans : ( ) (7) (7) -1

 

ans : (5) (7) (7) -1

 

 

이렇게 스택을 이용해서 O(N) 시간 안에 오큰수 배열을 구하였습니다.

 

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;

int n;
vector<int> v(1000001);
vector<int> ans(1000001);

stack<int> st;

int main()
{
    FASTio;
    cin >> n;

    for(int i=0;i<n;i++)
    {
        cin >> v[i];
    }

    st.push(v[n-1]);
    ans[n-1] = -1;

    
    for(int i=n-2;i>=0;i--)
    {        
        while(!st.empty() && st.top() <= v[i])
        {   
            st.pop();
        }

        if(st.empty())
        {
            st.push(v[i]);
            ans[i] = -1;
            continue;
        } else {
            ans[i] = st.top();
            st.push(v[i]);
        }
    }

    for(int i=0;i<n;i++)
    {
        cout << ans[i] << ' ';
    }


    return 0;
}