BOJ 17298 - 오큰수

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

 

예전에 풀었었고, 다시 풀어본 문제다.

처음 문제를 보고, 집가는 지하철에서 계속 생각하고, 잠자기 전에 계속 생각하다가 다음날 풀었을때 기분이 너무 좋았었다.

 

그런데 오랜만에 풀어보니 잘 풀리지 않고 몇번 틀렸다.

그래도 결국 다시 풀어냈다!

 

접근방식은 스택을 사용하여 스택의 top이 항상 새로나오는 수보다 큰 수를 유지하게 하는 거다.

(스택에는 내림차순으로 수가 저장되는 거다. 지금 설명으로는 애매한데, 밑의 설명과 코드를 보면 더 잘 이해가 될거다.)

 

먼저 정답배열을 전부 -1로 채워준다.

새로운 수와 스택의 top을 비교한다. 

새로운 수가 스택의 top보다 작다면, 오큰수가 아닌 거니깐 스택에 추가하고 넘어간다. 이때 새로운 수의 인덱스도 스택에 넣어준다. 

만약 새로 나온 수가 스택의 top보다 크다면, 그 수가 오큰수가 되므로 현재 스택의 top의 인덱스에 새로운 수를 저장하고 pop해준다.

이제 또 새로운 스택의 top과 새로운 수를 비교하고, top보다 크다면 위와 같이 오큰수가 되므로 스택의 top에 인덱스에 새로운 수를 저장하고 pop...

 새로운 수가 스택의 top보다 작을때까지 반복된다. 그리고 새로운 수가 스택의 top보다 작아지면, 스택에 새로운 수를 추가하고 다음 인덱스로 넘어간다.

 

 

#include <bits/stdc++.h>
using namespace std;
int n;
int a[10000004];
int ans[10000004];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    memset(ans, -1, sizeof(ans));
    stack<int> stk;
    stack<int> idxStk;
    for (int i = 0; i < n; i++)
    {
        if (stk.empty())
        {
            stk.push(a[i]);
            idxStk.push(i);
            continue;
        }
        if (stk.size() && stk.top() >= a[i])
        {
            stk.push(a[i]);
            idxStk.push(i);
        }
        else if (stk.size() && stk.top() < a[i])
        {
            while (stk.size() && stk.top() < a[i])
            {
                stk.pop();
                int idx = idxStk.top();
                idxStk.pop();
                ans[idx] = a[i];
                // cout << "idx : " << idx << ", a[i] : " << a[i] << ", ans[idx] : " << ans[idx] << "\n";
            }
            stk.push(a[i]);
            idxStk.push(i);
        }
    }

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

/*
7
4 3 2 1 2 3 4
-1 4 3 2 3 4 -1
*/

이게 이번에 푼 코드이고, 이걸 풀고나서 예전에 풀었던 코드를 봤는데 예전에 푼게 훨씬 깔끔하다...;;

 

#include <bits/stdc++.h>
using namespace std;
int n, num;
vector<int> v;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> num;
        v.push_back(num);
    }

    stack<pair<int, int>> stck; // {요소, index}
    stck.push({v[0], 0});

    vector<int> vv(n, -1);

    for (int i = 1; i < n; i++)
    {
        while (stck.size() && stck.top().first < v[i])
        {
            vv[stck.top().second] = v[i];
            stck.pop();
        }
        stck.push({v[i], i});
    }

    for (int i = 0; i < vv.size(); i++)
    {
        cout << vv[i] << " ";
    }

    return 0;
}

/*
4
3 5 2 7

ans : 5 7 7 -1

4
9 5 4 8

ans : -1 8 8 -1

4
5 1 2 7

ans : 7 2 7 -1

5
9 1 1 3 2

ans : -1 3 3 -1 -1
*/

 

 

 

 

시간은 거의 차이가 안나는데, 메모리는 예전에 푼게 훨씬 적게먹는다. 스택을 하나만 써서 그런듯하다.