Problem Solving
알고리즘 :: 백준 :: 2910 - 빈도 정렬
soreDemo
2025. 1. 7. 21:21
❔문제
🔄 문제 및 입출력 조건 파악
- 요소 개수: 1 ≤ N ≤ 1,000
- 각 요소의 최댓값(상한): 1 ≤ C ≤ 1,000,000,000
✏️ 문제풀이
빈도 정렬의 기준은 '많이 등장한 순'으로, 등장횟수가 같다면 '앞서 등장한 순'입니다.
즉, 각 숫자와 대응하는 인덱스의 값마다 아래와 같은 정보를 갖고 있어야 합니다.
- 이 숫자가 몇 번 등장했는지
- 이 숫자가 언제 처음 등장했는지
로직은 다음과 같습니다.
- 숫자를 입력받습니다. 등장횟수, 첫 등장 인덱스 번호 정보를 함께 저장합니다.
- 처음 등장했다면, 등장횟수는 1 입니다.
- 처음 등장한 숫자가 아니라면, 삽입하지 말고 등장횟수만 1 증가시킵니다.
- 문제에 나온 빈도 정렬의 기준에 따라 정렬합니다.
- 원하는대로 정렬시켜주는 STL 함수는 없기 때문에 따로 정렬 함수객체를 만들거나 람다함수를 만들면 됩니다.
어떤 컨테이너를 사용할지는 취향에 따라 다릅니다.
- `std::unordered_map<int, pair<int, int>>`로 한 번에 저장하기
- 숫자 / 등장횟수 / 첫 등장 인덱스 세 가지 정보를 하나의 컨테이너로 모두 처리합니다.
- 추후 정렬은 `std::vector`에서 이뤄지는데, 세 변수를 다루므로 `std::vector<tuple<int, int, int>>`를 사용하게 됩니다.
- `std::unordered_map<int, int>` 2개 사용하기
- { 숫자 / 등장횟수 } 정보를 저장하는 컨테이너와 { 숫자 / 첫 등장 인덱스 } 정보를 저장하는 컨테이너를 따로따로 만듭니다.
- 추후 정렬은 `std::vector`에서 이뤄지는데, { 숫자 / 첫 등장 인덱스 } 정보를 갖고있는 컨테이너가 따로 있기 때문에 우선 빈도 순으로만 정렬하기 위해 `std::vector<pair<int, int>>`를 사용하게 됩니다.
두 접근법 모두 장단이 있기 때문에 본인에게 편한 쪽으로 진행하면 됩니다.
📝 코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int N, C;
cin >> N >> C;
// key: 입력받은 숫자, value: <등장횟수, 첫 등장 인덱스 번호>
unordered_map<int, pair<int, int>> m;
for (int i = 0; i < N; ++i) {
int num;
cin >> num;
// 이미 값이 있다면, 등장횟수 1 증가 / 없다면 새로운 요소로 삽입
if (m.find(num) != m.end()) m[num].first++;
else m[num] = {1, i};
}
vector<tuple<int, int, int>> v;
v.reserve(m.size());
// map의 모든 요소를 vector에 넣는다.
for (const auto& it : m)
v.push_back({it.first, it.second.first, it.second.second});
// 등장횟수에 대해 내림차순 + 첫 등장 인덱스 번호에 대해 오름차순
sort(begin(v), end(v), [](const auto& lhs, const auto& rhs) {
if (get<1>(lhs) == get<1>(rhs)) return get<2>(lhs) < get<2>(rhs);
return get<1>(lhs) > get<1>(rhs);
});
// 모든 원소를 등장횟수만큼 반복해서 출력함.
for (const auto& it : v)
for (int i = 0; i < get<1>(it); ++i)
cout << get<0>(it) << ' ';
}
🕧 결과
