[BOJ 17299] 오등큰수

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

17299번: 오등큰수

문제 분석

• 오큰수와 매우 유사하다. ( https://genius00hwan.tistory.com/68 )
• 각 수 마다, 빈도수를 계산하여 그것을 기준으로 비교해야 한다.

[BOJ 17298] 오큰수

풀이 방식

• 기본적인 논리는 오큰수 문제와 동일하다.
• 1~1,000,000까지의 수가 들어올 수 있으므로 배열 A을 만들어 어떤 수 i가 들어 오면 A[i]의 값을 1 증가시켜준다.
• 빈도 수를 비교해 줘야 하므로 A[j],A[k] 방식으로 비교한다.

stack<int> ngf;//(오등큰수 후보들이 들어 있는 stack)
vector<pair<int, int>> arr; //(값과 오등큰수)
int freq[1000001]; // (빈도수)

int n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.emplace_back(x, -1);
        freq[x] += 1;
    }
    for (int i = (int) arr.size() - 1; i >= 0; i--) {
        int k = arr[i].first;
        while (!ngf.empty()) {
            int j = ngf.top();
            if (freq[j] > freq[k]) {
                arr[i].second = j;
                break;
            } else {
                ngf.pop();
            }
        }
        ngf.push(k);
    }
    for (int i = 0; i < n; i++) {
        cout << arr[i].second << " ";
    }
    return 0;
}

느낀 점

• 오큰수 문제와 매우 유사하다고 생각해 처음에는 좀 만만히 봤다.
• 그러다 빈도수를 비교해줘야 한다는 점에 대해 좀 고민을 해봤고, 처음엔 <map>을 사용해 입력된 수를 key로 하여 같은 값이 들어 올때마다 value를 증가시키는 방식을 사용하려 했다. -> 시간초과
• 입력되는 값의 모든 경우의 수에 맞춰 배열을 만들어 값을 증가 시키면 되겠다는 생각이 들었고 그 생각이 난 후에는 금방 문제를 해결했다.