BOJ - 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이다.
  • 입력 [ 3 5 2 7 ]
  • 출력 [ 5 7 7 -1 ]

구현

---

#include <iostream>
#include <stack>

using namespace std;
// 오큰수가 의미하는 것 
// NGE[1] ... 배열의 첫번째 인덱스의 오큰수를 의미함 
//            즉, 배열의 첫번째 인덱스 값에 존재하는 요소보다 큰 가장 왼쪽의 요소를 의미함. 
// 정답 백터

int main()
{
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    int num; 
    cin >> num;
    int OrderList[num]; // 입력값 저장 
    int answer[num];    // 출력값 저장 
    stack<int> TmpStack;

    for(int i=0; i < num; i++)
        cin >> OrderList[i];

    for(int i=num-1; i >= 0; i--)
    {   // 3 5 2 7
        while (!TmpStack.empty() && TmpStack.top() <= OrderList[i])
            TmpStack.pop();
        if(TmpStack.empty())
            answer[i] = -1;
        else
            answer[i] = TmpStack.top();// -1 7 7 5  
        TmpStack.push(OrderList[i]); // 7 5 3
    }

    for(auto &el : answer)
        cout << el << " ";
    cout << endl;
}

SOL

---

• 입력된 수열을 배열로 받는다.

    for(int i=0; i < num; i++)
        cin >> OrderList[i];

• 배열로 입력받은 수열의 끝부터 역순으로 하나씩 임시 스택에 넣는다.

  역순으로 받아야 스택의 pop, push를 적절하게 사용할 수 있기 때문.

  TmpStack.push(OrderList[i])

• 임시스택이 비어있지 않고, 임시스택의 top값과 역순의 입력 값을 비교 하였을 때 역순의 입력값이 크면

  • 임시스택 ... pop
    - 임시스택이 비었으면 ... (처음 루프문을 돌 경우에도 적용)
    - answer[i] = -1;
    - 임시스택이 비어있지 않으면
    - answer[i] = TmpStack.top()

      for(int i=num-1; i >= 0; i--)
      {   // 임시스택이 비어있지 않고, 오큰수값 TmpStack.top()이 나올때 까지 
          while (!TmpStack.empty() && TmpStack.top() <= OrderList[i])
              TmpStack.pop();
          if(TmpStack.empty())
              answer[i] = -1;
          else
              answer[i] = TmpStack.top();// -1 7 7 5  
          TmpStack.push(OrderList[i]); // 7 5 3
      }

Work flow

---

n = 4

임의의 수열 : [ 3 5 2 7 ]

i = 0

TmpStack [ ]

OrderList [ 7 ]

TmpStack.empty()

answer[ i ] = -1

TmpStack.push( 7 )

i = 1

TmpStack[ 7 ]

OrderList [ 2 ]

! TmpStack.empty()

! TmpStack[ 7 ] ≤ OrderList[ 2 ]

answer[ i ] = TmpStack[ 7 ]

TmpStack.push( 2 );

i = 2

TmpStack[ 7 2 ]

...

알게된 점

---

스택문제는 스택으로 푸는 이유가 있다..

Reference & 다른 PS 모음집

---

https://github.com/ggh-png/PS

STACK & QUEUE