[BOJ/백준] 17299 오등큰수

● [문제번호 17299] 오등큰수

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

17299번: 오등큰수

 

● 알아야 할 것

: stack, vector 자료구조와 메소드

 

● 풀이 과정

: 전 단계 문제의 풀이를 활용 (참고 할 것 링크)

: 그러나 '등장횟수 구하기' 와 'index -> v[ index ] -> cnt[ v[ index ] ]'  주의

 

● 주의 할 것

: 입력 된 vector의 각 원소 등장 횟수를 구할 때 주의

주어진 입력 배열의 크기와 입력 배열의 원소 최댓값을 고려

: 등장횟수를 알려면 index를 입력 배열 vector를 거쳐 와야한다. (주석 참고)

 

● 참고 할 것

: (전단계 문제 풀이에서 힌트) https://pirateturtle.tistory.com/167

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 자신보다 등장 횟수가 많은 수를 구하기 위한 stack
// 값이 아닌 vector의 index를 저장
stack<int> s;
// 입력 저장을 위한 v / 등장 횟수 저장을 위한 cnt / 결과 저장을 위한 result
vector<int> v, cnt, result;
int N;

// 오등큰수를 구하기 위한 작업
void NGF(int index)
{
    // [17298 오큰수] 문제와 달라진 점      ★
    // v[s.top()] -> cnt[v[s.top()]]
    // v[index] -> cnt[v[index]]
    // cnt의 값은 v[index]로 찾는다
    while(!s.empty() && cnt[v[s.top()]] < cnt[v[index]])
    {
        result[s.top()] = v[index];
        s.pop();
    }
    
    // 현재 index 쌓기
    s.push(index);
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    v.assign(N, 0);
    // 수열의 크기 확인     ★
    // 수열의 원소값 <= 수열의 크기 이므로 수열의 index를 활용
    // 안그러면 입력값의 등장 횟수를 구할 때 O(N^2)로 '시간초과' 결과를 가져옴
    cnt.assign(1000001, 0);
    result.assign(N, -1);
    
    // 입력 + 등장횟수 세기
    for(int n = 0; n < N; n++)
    {
        cin >> v[n];
        cnt[v[n]]++;
    }
    
    // 오등큰수 함수 호출
    for(int n = 0; n < N; n++)
        NGF(n);
    
    // 결과값 vector 전체 출력
    for(int n = 0; n < N; n++)
        cout << result[n] << " ";
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [201 - 자료구조 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	17413	단어 뒤집기 2	https://pirateturtle.tistory.com/165
2	10799	쇠막대기	https://pirateturtle.tistory.com/166
3	17298	오큰수	https://pirateturtle.tistory.com/167
4	17299	오등큰수	https://pirateturtle.tistory.com/168