[C/C++] 17299번 - 오등큰수

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

왠지 모르게 골드 3이라는 난이도 때문에 예전에 풀 의지를 느끼지 못했던 문제인데, 차근히 풀어보니 그렇게 어려운 문제는 아닌 스택 문제이다.

문제 이해

길이가 N인 수열이 있을 때 i번째 원소를 x원소라고 해보자.

이 때, '자기랑 같은 숫자가 배열 안에 등장한 횟수'가 F(x)의 값이다.

[1 1 2 3 4 2 1]이라는 배열이 있다면 x=1일 때, F(1) = 3이라는 것이다. (1이 배열에서 3번 등장했으므로)

그렇다면 이 때 '오등큰수'는 배열에서 자기보다 오른쪽에 있으면서 F(x) 값이 자기보다 큰 최초의 x이다.

만약 그러한 x가 없다면, 그 수의 '오등큰수'는 -1이 된다.

위와 같은 조건을 가질 때, 배열의 모든 원소의 '오등큰수'를 찾는 문제이다.

 

문제 해설

우선 각 원소가 배열에서 등장한 횟수를 먼저 구해야함은 자명하다. (어차피 N개의 원소를 확인해서 등장 횟수를 구해야 문제 진행이 가능하기에)

그렇게 구한 원소의 등장 횟수를 가지고 왼쪽부터 각 원소의 오등큰수를 확인해야 하는데, 이를 위해 하나의 스택을 이용할 것이다.

이 스택에는 원소의 F(x)값을 넣을 것이다.

가장 왼쪽 원소부터 시작해서 아래의 과정을 거친다.

1. 자신의 F(x)를 넣기 전에 스택의 가장 위의 값이 자기 자신의 F(x) 보다 작은지 확인한다.

1-1. 만약 스택이 비어있지 않고, 자기 자신의 F(x)보다 작다면, 내가 그 스택에 F(x)를 넣은 원소의 오등큰수인 것이다. 그렇기에 스택에서 pop 하고 그 pop 한 원소의 오등큰수로 나의 x를 적어놓는다.

위의 과정을 스택이 비거나, 스택의 가장 위의 값이 자기 자신의 F(x)보다 크거나 같을 때까지 진행한다.

2. 과정이 끝나거나 조건을 만족하지 않아 그냥 지나쳤다면 이제 스택의 top에 자기 자신의 F(x)를 집어넣는다.

이 과정을 배열 원소의 끝까지 진행하고 나면 아직 스택에 F(x)는 들어가 있는데 오등큰수는 정해지지 않은 원소들만 남는다.

이 원소들은 자기보다 F(x) 값이 큰 수가 오른쪽에 존재하지 않는 것이므로, -1을 오등큰수로 지정해 준다.

이렇게 구한 결과를 순서대로 출력해 주면 된다.

 

코드

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int cnt[1000001] = {0,};
int ans[1000001] = {0,};

int main() {
    int N;
    vector<int> arr;
    vector<pair<int,int>> v; // {odk, origin idx}
    scanf("%d", &N);
    for (int i=0;i<N;i++) {
        int inp;
        scanf("%d", &inp);
        arr.push_back(inp);
        cnt[inp]++;
    }
    for (int i=0;i<N;i++) {
        int odk = cnt[arr[i]];
        while (!v.empty() && v.back().first < odk) {
            pair<int,int> p = v.back();
            v.pop_back();
            ans[p.second] = arr[i];
        }
        v.push_back({odk, i});
    }
    while (!v.empty()) {
        pair<int,int> p = v.back();
        v.pop_back();
        ans[p.second] = -1;
    }
    for (int i=0;i<N;i++) {
        printf("%d ", ans[i]);
    }
}