[백준] 17299 오큰등수

문제 설명

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

17299번: 오등큰수

크기가 n인 수열이 주어질 때, 각 원소의 오등큰수를 구하기

오등큰수는 오른쪽에 있으면서 수열에서 등장한 횟수가 큰 수 중에서 가장 왼쪽에 있는 수

그러한 수가 없으면 오큰등수는 -1

 

문제 풀이법

[백준 17298 오큰수] 문제와 매우 유사하다

다른점은 원소의 크기가 아닌, 원소의 횟수를 따로 저장해서 비교해 주어야 한다는 점이다

 

• 수열을 담을 vector<int> v
• monotone stack을 활용할 stack<int> s
• 원소의 등장 횟수를 담을 vector<int> cnt
  • 이때 미리 1000001만큼 0으로 초기화 해주어야 한다 (원소의 최댓수가 1000000이므로)
• 답을 담을 vector<int> ans

이 4개가 필요하다

 

• 수열을 입력 받으면서 v에 담고, cnt[v[i]] + 1를 해준다
• 맨 뒤에서부터 스택에 대해 내림차순(가장 큰 수가 먼저 들어감) 연산을 한다
  • 만일 스택이 비어있다면 오등큰수가 없으므로 바로 ans에 -1을 넣는다
  • 스택이 비어있지 않다면, 스택이 비지 않거나, 스택의 top이 나온 횟수가 원소가 나온 횟수보다 크지 않을 때 까지 pop하며 while문을 돈다
  • 다 돌았을 때, 비어있다면 오큰등수가 없는 것이므로 ans에 -1을 넣는다
  • 비어있지 않다면 스택의 top이 나온 횟수가 오큰등수이므로 ans에 넣는다
• 연산이 끝나면 ans의 값을 출력한다

 

 

소스 코드

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main()
{   
    int n;
    cin >> n;
    
    stack<int> s;
    vector<int> v(n + 1, 0);
    vector<int> cnt(1000001, 0);
    vector<int> ans(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        int tmp;
        cin >> tmp;
        v[i] = tmp;
        cnt[tmp]++;
    }
    
    for (int i = n; i > 0; i--)
    {
        if (!s.empty())
        {
            while (!s.empty())
            {
                if (cnt[s.top()] > cnt[v[i]])
                    break;
                s.pop();
            }
            if (s.empty())
                ans[i] = -1;
            else    
                ans[i] = s.top();
        }
        else
            ans[i] = -1;
            
        s.push(v[i]);
    }
    
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);

    return 0;
}