[BOJ알고리즘, C++]#17299_오등큰수, 스택, unordered_map

 

[BOJ알고리즘, C++]#17299_오등 큰 수

 

BOJ 알고리즘 문제 풀이, 17299번 문제 "오등 큰 수"

C++의 STL이 제공하는 stack과 unordered_map 컨테이너를 활용하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

 

#2. 풀이

1. 스택

[자료 구조]#0_선형 자료구조

 

[Basic C++] #64_stack

 

Details

 

• 스택은 LIFO(후입선출) 방식으로 동작하는 선형 자료구조입니다.
• 스택은 같은 구조와 같은 크기의 데이터를 정해진 한 방향으로만 삽입/삭제가 가능한 자료구조입니다.

 

2. unordered_map

[Basic C++] #41_unordered_map, 비순차 연관 컨테이너

 

[Basic C++] #40_해시함수, 비순차 연관 컨테이너, 해시 테이블

 

Details

 

• C++의 STL이 제공하는 "unordered_map"은 지정된 형식의 Key와 Value를 한 쌍으로 해시 테이블 자료구조에 저장하는 비 순차 연관 컨테이너입니다.

 

3. 등장 횟수 -> unordered_map, 오름차순 유지 -> stack

[BOJ알고리즘, C++]#17298_오큰수, 스택

 

Details

 

1. 위 문제와 비슷하지만, 하나 변경된 조건은 현재 위치의 원소보다 오른쪽에 위치하며, 배열에 그 등장 횟수가 더 많으며, 가장 왼쪽에 위치한 원소를 찾는 문제입니다.
2. 배열을 역순으로 순회하며 stack에 push 하고, 배열의 현재 위치의 값과 stack의 top을 비교하는 작업은 동일하지만, 우리는 그 값의 크기가 아닌, 배열에 등장하는 횟수를 비교합니다. 따라서, 주어진 배열을 전달받고, "unordered_map"을 활용해 원소의 등장 횟수를 먼저 카운팅 합니다.
3. 이후, 배열을 역순으로 순회하며 stack에 push 하며, stack의 top과 배열의 현재 위치의 원소를 "Key" 값으로 하여 unordered_map을 통해 "Value(등장 횟수)"를 가져와 비교하는 작업을 수행합니다.
4. 이 외 모든 작업들은 17298번 문제와 동일합니다.

 

#3. 코드

 

#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N;
    
    cin >> N;
    
    vector<int> seq(N);
    vector<int> ans(N);
    unordered_map<int, int> um;
    stack<int> s;
    
    for(int i=0; i<N; i++)
    {
        cin >> seq[i];
        um[seq[i]]++;
    }
    
    for(int i=N-1; i >= 0; i--)
    {
        while(!s.empty() && um[seq[i]] >= um[s.top()])
            s.pop();
        
        if(s.empty()) ans[i] = -1;
        else ans[i] = s.top();
        
        s.push(seq[i]);
    }
    
    for(int i=0; i<N; i++)
        cout << ans[i] << ' ';
    
    return 0;
}