문제

---

17298 - 오큰수

풀이

알고리즘

---

1. 수열 A의 크기만큼 반복한다.
   a. 스택이 비어있지 않으면서 스택의 top이 A[i] 보다 작다면(즉, 오큰수를 찾았다면),
   A[stack.top()] = A[i]로 변경해주고 stack을 pop해준다.
   b. 일반적인 경우에 현재 index를 스택에 push한다.
2. stack에 남아있는 오큰수를 찾지 못한 index의 원소들은 모두 -1로 변경해준다.

그려서 설명하자면...

아래 그림에서 i 화살표는 index의 포인터를, s 화살표는 stack.top()의 포인터를 나타낸다고 보면 된다.

코드

---

#include <bits/stdc++.h>
using namespace std;

int N;

void Solve(vector<int> &A)
{
    stack<int> myStack;

    for (int i = 0; i < N; i++)
    {
        while (!myStack.empty() && A[myStack.top()] < A[i])
        {
            A[myStack.top()] = A[i];
            myStack.pop();
        }

        myStack.push(i);
    }

    while (!myStack.empty())
    {
        A[myStack.top()] = -1;
        myStack.pop();
    }

    for (int i = 0; i < N; i++)
        cout << A[i] << ' ';
}

int main()
{
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++)
        cin >> A[i];

    Solve(A);
}

주석코드

---

#include <bits/stdc++.h>
using namespace std;

int N;

void Solve(vector<int> &A)
{
    stack<int> myStack;

    // 수열 A의 크기만큼 반복
    for (int i = 0; i < N; i++)
    {
        // 스택이 비어있지 않고, A[myStack.top()]이 A[i]보다 작을 때
        while (!myStack.empty() && A[myStack.top()] < A[i])
        {
            A[myStack.top()] = A[i];
            myStack.pop();
        }

        // 그 외의 경우에는 인덱스 i 를 스택에 push
        myStack.push(i);

        ////////////////////////////////////////////////////////

        cout << "i = " << i << endl;

        cout << "A = ";
        for (int idx : A)
            cout << idx << ' ';
        cout << "\n";

        stack<int> temp = myStack;
        cout << "S = ";
        while (!temp.empty())
        {
            cout << temp.top() << ' ';
            temp.pop();
        }
        cout << "\n\n";

        ////////////////////////////////////////////////////////
    }

    // 오큰수를 찾지 못한 원소는 -1로 변경
    while (!myStack.empty())
    {
        A[myStack.top()] = -1;
        myStack.pop();
    }

    for (int i = 0; i < N; i++)
        cout << A[i] << ' ';
}

int main()
{
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++)
        cin >> A[i];
    cout << endl;
    Solve(A);
}

테스트케이스 출력

---

4
9 5 4 8

i = 0
A = 9 5 4 8
S = 0

i = 1
A = 9 5 4 8
S = 1 0

i = 2
A = 9 5 4 8
S = 2 1 0

i = 3
A = 9 8 8 8
S = 3 0

-1 8 8 -1

참고한 글

[백준] 17298번 : 오큰수 - JAVA [자바]

여담

백준 스택 단계의 마지막 문제다. 그 전 문제까지는 사실 스택을 사용할 줄 아느냐의 차원의 문제였는데, 마지막 문제만큼은 활용을 할 수 있냐를 물어보는 듯한 문제였다. 한시간정도 고민하다가 결국 구글링을 통해서 풀었다...
아마 구글링 없이는 하루종일 고민했어도 못풀었을 듯하다.

효율성 상관없이 푸는 방법은 아마 모두 알겠지만, 이중 for문을 돌리면 된다. 다만 당연히 시간복잡도가 O(N^2)이므로 통과할 수 없다.

풀이를 보면서 풀고나서도 뭔가 머릿속에 완벽히 들어오지가 않아서 포스팅을 하면서 부족한 부분을 채우고자 했고, 아마도 성공한 듯 하다.

위의 그림을 보면 알겠지만, 풀이가 투포인터와 비슷한 성질도 갖고 있다는 느낌에 이런 식으로 풀이를 진행해봤다. 여러분에게도 와닿았을지는 모르겠다. 참고한 글을 보고도 이해가 잘 안된다면 이 포스팅도 같이 본다면 도움이 될 것이다.