이번에는 백준 2910번 빈도 정렬 문제를 풀어보았습니다.
이 문제는 단순히 숫자를 정렬하는 것이 아니라, 숫자가 등장한 횟수를 기준으로 정렬해야 하고,
등장 횟수가 같다면 먼저 나온 숫자가 앞에 와야 하는 문제였습니다.
즉, 숫자 하나에 대해 단순 값만 저장하는 것이 아니라
- 어떤 숫자인지
- 몇 번 등장했는지
- 처음 몇 번째에 등장했는지
를 함께 관리해야 했습니다.
문제 설명
길이 N의 수열이 주어집니다.
이 수열을 빈도 정렬해서 출력하면 됩니다.
정렬 기준은 다음과 같습니다.
- 더 많이 등장한 숫자가 앞에 온다.
- 등장 횟수가 같다면, 더 먼저 등장한 숫자가 앞에 온다.
즉, 단순 오름차순/내림차순 정렬이 아니라
빈도와 입력 순서를 함께 고려한 정렬 문제입니다.
풀이 아이디어
이 문제에서는 각 숫자에 대해 다음 세 가지 정보를 함께 저장했습니다.
- 입력 숫자
- 입력 숫자의 개수
- 입력 숫자가 처음 등장한 순서
이를 위해 map<int, tuple<int, int, int>>를 사용했습니다.
즉, key는 숫자이고, value에는
(입력 숫자, 입력 숫자 개수, 입력 숫자의 입력 순서)를 저장하는 방식입니다.
입력을 모두 받은 뒤에는 map에 담긴 value들만 ret 벡터에 옮겨 담고,
이 벡터를 문제의 정렬 기준에 맞게 정렬해서 출력했습니다.
코드
#include <bits/stdc++.h>
using namespace std;
bool sorting_algorithm(tuple<int, int, int> a, tuple<int, int, int> b) {
if (get<1>(a) != get<1>(b)) {
return get<1>(a) > get<1>(b);
}
return get<2>(a) < get<2>(b);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N,C;
cin >> N >> C;
//입력 숫자, 입력 숫자 개수, 입력 숫자의 입력순서
map<int, tuple<int, int, int> > m;
vector<tuple<int, int, int> > ret;
for (int i = 0; i < N; i++) {
int temp;
cin >> temp;
if (m.find(temp) != m.end()) {
get<1>(m[temp])++;
} else {
m[temp] = {temp, 1, i};
}
}
for (auto it : m) {
ret.push_back(it.second);
}
sort(ret.begin(), ret.end(), sorting_algorithm);
for (auto it : ret) {
for (int i=0; i<get<1>(it); i++) {
cout << get<0>(it) << " ";
}
}
return 0;
}풀이 흐름
N,C를 입력받는다.- 각 숫자를 입력받으면서 map에
- 숫자
- 등장 횟수
- 처음 등장한 순서
를 저장한다.
- map에 저장된 값들만
ret벡터에 옮긴다. ret을- 등장 횟수 내림차순
- 처음 등장한 순서 오름차순
으로 정렬한다.
- 정렬된 결과를 등장 횟수만큼 반복 출력한다.
구현 포인트
1. map의 value에 숫자, 개수, 순서를 함께 저장
이 문제는 숫자 하나에 대해 정보가 여러 개 필요했습니다.
그래서 map의 value를 tuple<int, int, int>로 두고,
get<0>: 입력 숫자get<1>: 입력 숫자 개수get<2>: 입력 숫자의 입력 순서
를 저장했습니다.
map<int, tuple<int, int, int> > m;이렇게 하면 숫자별로 필요한 정보를 한 번에 관리할 수 있습니다.
2. 이미 나온 숫자면 개수만 증가
입력을 받을 때 같은 숫자가 다시 등장하면 개수만 증가시키면 됩니다.
if (m.find(temp) != m.end()) {
get<1>(m[temp])++;
} else {
m[temp] = {temp, 1, i};
}처음 등장한 순서는 첫 입력 때만 저장하고,
그 이후에는 개수만 늘리도록 했습니다.
3. 정렬 기준은 두 가지
정렬은 sorting_algorithm() 함수로 처리했습니다.
bool sorting_algorithm(tuple<int, int, int> a, tuple<int, int, int> b) {
if (get<1>(a) != get<1>(b)) {
return get<1>(a) > get<1>(b);
}
return get<2>(a) < get<2>(b);
}즉,
- 등장 횟수가 다르면 더 많이 나온 숫자가 앞에 오고
- 등장 횟수가 같으면 더 먼저 입력된 숫자가 앞에 옵니다.
문제 조건을 그대로 comparator로 옮긴 부분입니다.
4. 정렬 후에는 개수만큼 반복 출력
정렬이 끝난 뒤에는 각 숫자를 등장 횟수만큼 출력하면 됩니다.
for (auto it : ret) {
for (int i=0; i<get<1>(it); i++) {
cout << get<0>(it) << " ";
}
}즉, 정렬된 정보는 숫자 하나당 한 번씩만 들어 있지만,
출력은 실제 빈도만큼 반복해서 해주어야 합니다.
5. 이번에 정리하게 된 tuple
이 문제를 풀면서 tuple 개념도 같이 정리하게 되었습니다.
이번 코드에서는 하나의 숫자에 대해 여러 정보를 함께 저장해야 했기 때문에 tuple이 잘 맞았습니다.
사용할 때는 아래처럼 인덱스로 접근할 수 있습니다.
get<0>(name)
get<1>(name)
get<2>(name)값을 넣을 때는
{a, b, c}형태로 한 번에 넣을 수 있었습니다.
즉, 여러 개의 값을 하나의 묶음처럼 다뤄야 할 때 tuple을 사용할 수 있다는 점을 이 문제에서 다시 확인할 수 있었습니다.
