[백준][C++] 17299: 오등큰수

 

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

17299번: 오등큰수

 

 

 

 

 

---

- 문제

 

https://stopthebackspace.tistory.com/130

 

  위의 오큰수 문제에서 큰지 작은지 판별하는 걸 숫자가 나온 횟수로 바꾼 문제다.

 

 

---

- 해설

오큰수 문제를 푼 방식 그대로 map을 이용해서 카운팅을 해 줬는데, 시간초과가 나왔다.

 

 

그래서 그냥 배열을 이용해서 카운팅해봤는데 잘 풀렸다.

 

 

 

---

- 풀이

#include <iostream>
#include <stack>
// #include <map>
using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    int A[1000001];
    int answer[1000001];
    int m[1000001] = {0};
    stack<int> s;
    // map<int,int> m;
    
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i];
        m[A[i]]++;
    }
    for(int i = N - 1; i >= 0; i--){
        while(1){
            if(s.empty()){
                answer[i] = -1;
                s.push(A[i]);
                break;
            }
            else if(m[s.top()] > m[A[i]]){
                answer[i] = s.top();
                s.push(A[i]);
                break;
            }
            else{
                s.pop();
            }
        }
    }
    for(int i = 0; i < N; i++){
        cout << answer[i] << ' ';
    }
    
    
    return 0;
}

 

 

---

- 새롭게 알게 된 점