[BOJ] 17299 오등큰수 C++ 문제풀이 & 소스코드

Info

난이도 : GOLD3

유형 : DataStructure

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

소스코드 : https://github.com/novvvv/PS/blob/main/BOJ/2025/C++/17299.cpp

---

Solve

문제분석

F(Ai) - Ai가 수열A에서 등장한 횟수. 

Ai의 오등큰수 - 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중 가장 왼쪽에 있는 수. 그러한 수가 없으면 오등큰수는 -1

 

a[] : 크기가 n인 수열

freq[] : ai가 몇 번 등장했는지 빈도를 저장할 수열

ngf[] : 각 원소의 오등큰수 정보를 저장할 수열 

int a[max_val], freq[max_val], ngf[max_val];

 

수열의 정보를 입력함과 동시에 해당 원소의 빈도를 증가시킨다.

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        freq[a[i]]++;
    }

 

수열 a를 반대로 순회하여 원소를 차례로 스택에 집어넣는다. 

만약 스택이 비어있지 않고, 스택의 최상단에 있는 원소의 빈도 (freq[stk.top()]) 보다 현재 넣으려고 하는 원소의 빈도 (freq[a[i]]) 보다 작거나 같다면 스택에서 원소를 제거한다.

 

1 1 2 [3 4 2 1] 을 예시로 들어보면

원소 3의 경우 빈도가 1이고, 원소 4 또한 빈도가 1이다. 따라서 원소 4를 스택에서 제거한다. 

 

1 1 2 [3 2 1] 

원소 3의 빈도 (1) 보다 원소 2의 빈도 (2)가 더 크기에 원소 3의 ngf는 스택의 최 상단인 2가 된다.

왜냐하면 ngf의 정의를 보면 3보다 우측에 존재하면서 빈도가 3보다 크고 가장 왼쪽에 존재하는 원소는 2이기 때문이다. 

* 스택의 최상단에 존재하는 원소는 항상 i번째 원소의 ngf를 만족한다. 

 

스택이 비어있다면 오른쪽에 빈도가 더 높은 수가 없다는 뜻이니 ngf를 -1로 초기화한다. 

 

    stack<int> stk;
    for (int i = n - 1; i >= 0; i--) {
        while(!stk.empty() && freq[stk.top()] <= freq[a[i]]) stk.pop();
        if (stk.empty()) ngf[i] = -1; // 스택이 비어있다? -> 오른쪽에 빈도가 더 높은 수가 없다. (-1)
        else ngf[i] = stk.top();
        stk.push(a[i]);
    }