[자료구조] 백준 17298번 오큰수(C++)

https://www.acmicpc.net/problem/17298

 

해당 문제는 입력된 수열을 돌면서 해당하는 숫자에서 오른쪽에 있으면서 해당 숫자보다 더 크고 가장 왼쪽인 숫자를 구하라는 것이다

 

예를 들어 3 5  8 7 에 대해서

3에서 오른쪽에있으면서 큰 숫자는 5 8 7인데 가장 왼쪽에 있는 숫자는 5이니, 3의 자리에는 3가 출력되어야 한다는 뜻이다.

 

여기서, 가장 먼저 간단하게 어? 처음부터 돌면서 해당 숫자에 대해서 그 다음 숫자들을 다 돌면 되는 거 아니야? 라고 생각이 들겠지만 시간제한은 1초인데 반해 수열의 크기가 백만이다. 즉 시간복잡도가 n을 넘으면 안될 것이다.

 

그렇다면 이것을 어떻게  풀까?

 

앞에서 말한 2개의 반복문을 사용하는 것은 앞서말한 시간 복잡도 이슈로 불가능 할 것이다.

 

한번 해볼까? 남자란 자고로 부딪혀봐야 깨달을 수 있기 때문이다.

 

#include <iostream>

#include <stack>

using namespace std;

int main()

{

    int c;

    cin >> c;

    int arr[c];

    int result[c]; // 오큰수를 저장할 배열

 

    for (int i = 0; i < c; i++) // 입력받기

    {

        cin >> arr[i];

    }

    int sig = 0;

    for (int i = c - 1; i >= 0; i--)

    {

        for (int j = i + 1; j < c; j++)

        {

            sig = 1;

            if (arr[i] < arr[j])

            {

                result[i] = arr[j];

                break;

            }

            sig = 0;

        }

        if (sig == 0)

            result[i] = -1;

    }

    for (int i = 0; i < c; i++)

    {

        cout << result[i] << " ";

    }

    cout << "\n";

    return 0;

}

이런 젠장

역시 사람은 맞아봐야 그때 잘못된 것을 깨닫는 것 같다.

 

테스트 케이스들은 모두 통과하였지만 대략 38%쯤 틀렸다고 떳다.

 

아마 이 내부 for문 때문에 nlogn이되어 실패가 뜨는 것 같은데,,,

 

어찌되었든 그 값을 비교하기 위해서는 for문 , while문 은 두번은 돌아야 하긴 한다.

근데 이 값을 혁신적으로 줄여주기 위한 방법이 뭐가있을까

 

그런당신을위해 준비했습니다

stack!

 

#include <iostream>

#include <stack>

using namespace std;

int main()

{

    int c;

    cin >> c;

    int arr[c];

    int result[c]; // 오큰수를 저장할 배열

    stack<int> st;

    for (int i = 0; i < c; i++) // 입력받기

    {

        cin >> arr[i];

    }

   

    for (int i = c - 1; i >= 0; i--)

    {

        while (!st.empty() && st.top() <= arr[i])

            st.pop();

        if (st.empty())

            result[i] = -1;

        else

            result[i] = st.top();

        st.push(arr[i]);

    }

    for (int i = 0; i < c; i++)

    {

        cout << result[i] << " ";

    }

    cout << "\n";

    return 0;

}

웜마

이게 뭔소린가 싶을것이다

 

대충 여기서 사용한 원리는

 

1. 스택에는 결과값에 -1이 아닌 값들이 들어있다 ( 자신의 숫자보다 큰 숫자가 오른쪽에 존재하는 경우)

2. 만약 스택이 비어있지 않고, 스택의 탑이 현재 값보다 작다면 그 값을 버린다

3. 반복문 이후 스택이 비어있지 않다면 스택의 탑을 결과값에 넣어주는 것이다.

4. 이후 현재 값을 스택에 넣어준다.

    =스택의 탑에 해당값이 들어가면 가장 먼저 비교하는 값이 가장 왼쪽에 있는 값이기 때문에

문제에서 요구하는 오른쪽에있으면서 가장 왼쪽에 있는 값을 넣게 되는 것과 같다.

 

 

뭔가 직관적으로 이해가 안될 것이다

숫자를 예를들어 보자

 

9 5 4 8이란 값이 들어올때

 

처음 들어오는 반복문에서는 8이란 값에 대해 먼저 볼 것이다.

while문의 경우 stack에는 아무런 값이 없으니 지나가고

스택또한 비어있으니 -1 값을 넣어주게 되며

현재 값을 스택에 넣어준다

 

그렇다면

스택에는 8 하나의 값만 들어가게 될 것이다.

마지막에 스택에 현재 값을 넣어주는 이유는, 이후 마주하는 숫자들에 대해서, 다음값들과 비교하기 위해서 넣는 것이다

그럼 다음값인 4를 넣어보자

 

while (!st.empty() && st.top() <= arr[i])

            st.pop();

 

 

4는 해당 문에서 top(8)보다 작으므로 자연스레 넘어가게 된다.

그럼 당연히 

if (st.empty())

            result[i] = -1;

        else

            result[i] = st.top();

를 통해 result에는 top값이 들어가게 된다

그다음 push를통해 4를 넣어준다

그렇다면 스택은 이렇게 되어 있을 것이다.

그럼 5가 들어와서 처음으로 하는 일은 top인 4와 비교를 하는 것인데

 

5 > 4 이므로

4는 pop을통해 날라가고 다시 스택은

 

만 남게 된다.

 

여기서 살짝 의문일 수 있다.

4를 날리면 이후 나오는 값들에 대해서는 .. 어떻게 비교를 하지?

나도 그렇게 생각했는데 

 

"오른쪽에있으면서도 가장 큰 왼쪽값들에 대해서는 5가 이미 가장 크므로, 4는 추후 비교할일이 없다"

 

사실 똑똑하신 분들은 말 안해도 쉽게 이해할 수 있는데, 나 같은 경우는 스택을 처음 다뤄봤었을때 풀었던 문제이고,

직관적인 표현을 좋아해서인지 이해가 쉽지 않았다.

쨋든

계속 다음 while문에서 8을 만나서 while문 나오고나면 저번값과 같이

8 넣고, 스택에 5넣는다

다음 9를보자

 

9를만났을때 스택은

이제 말안해도 알것이다 while문에서 9가 5보다 크므로 out

어라 근데 9가 8보다 큰데..? 그럼 너도 아웃

그럼 스택은 빈상태가 된다.

 

이제 stack이 비었을때는 뭐라고??

-1이 나와야 된다

(왜냐면 오른쪽에 있는 값중에 자신보다 큰 값이 없기 떄문)

 

스택에는 이제 9만 넣어주고 끝나고

그래서 답은 -1 8 8 -1이 나오게 되는 것이다..

 

stack에 답을 넣을때는 오른쪽에 있는 값들 중 현재값보다 클 수 있는 값들의 후보군인것이다!