[C++]백준 - 17298번 문제

17298번: 오큰수 (acmicpc.net)

17298번: 오큰수

 

17298번 : 오큰수

---

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

입력

---

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

 

 

출력

---

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

 

---

 

생각해 볼 점

---

입력값의 마지막부터 역순으로 진행될 내용이므로, 입력을 Input 스택에 받습니다.

 

오큰수를 담는 OKS 스택과 결과를 담은 Result 스택을 더 준비합니다.

 

예시)

입력 : {3 5 2 7}

 

1. Input 스택에 3,5,2,7을 차례로 담습니다.

2. Input 스택의 top을 확인하고 OKS 스택 중 top보다 큰 숫자가 나올 때까지 pop을 진행합니다.

3. OKS 스택에서 큰 숫자를 발견하지 못했다면 -1을 result에 담고, 있다면 해당 숫자를 담습니다.

4. OKS 스택에 Input 스택의 top을 담고, Input 스택의 pop을 진행합니다.

 

5. Input 스택이 빌 때까지 2~4를 반복합니다.

 

코드

---

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    int N;
    cin >> N;
    stack<int> st, oks, result;		//스택, 오큰수, 결과
    for(int i = 0; i < N; i++)
    {
        int input;
        cin >> input;
        st.push(input);				//입력 값 스택에 담기
    }
    while(!st.empty())				//스택이 빌 때까지
    {
        while(!oks.empty() && oks.top() <= st.top()) oks.pop();	//오큰수 찾기
        if(oks.empty()) result.push(-1);		//없으면 -1
        else result.push(oks.top());			//있으면 오큰수
        oks.push(st.top());				//오큰수 새로 담기
        st.pop();
    }
    while(!result.empty())
    {
        cout << result.top() << " ";
        result.pop();
    }
    return 0;
}

 

그 외

---