https://www.acmicpc.net/problem/2910
2910번: 빈도 정렬
첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다.
www.acmicpc.net
풀이 과정
여러 개의 수가 주어질 때, 출현 빈도의 내림차순으로, 동일한 경우 먼저 출현한 순으로, 수를 정렬하는 문제이다. map<ll, int> 와 vector<pair<ll, int>>를 이용해서 풀었다. map에 input값을 넣으면 vector의 인덱스 번호가 나오고 해당 번호에서 입력값과 출현 횟수를 볼 수 있는 방식이다. 동일한 요소가 들어 왔을 때, map을 사용하기 때문에 더 빠르게 접근할 수 있지 않을까 생각했다. 그리고 stable_sort()와 cmp() 함수를 구현해 pair<ll, int>의 second값을 기준으로 내림차순 정렬로 만들었다. stable_sort() (병합 정렬)는 일반 sort() (퀵 정렬)와 다르게 동일한 값을 가진 요소에 대해 기존 순서를 보장함으로 동일한 출현 횟수를 가질 경우 먼저 출현한 수를 출력할 수 있다.
느낀 점
map<ll, int>과 vector<pair<ll ,int>>로 감을 잡는데 어려웠다. C가 크지만 N이 1000으로 작기 때문에 굳이 map을 사용하지 않고 두 개의 vector를 이용해서 풀 수도 있었다. 또 sort()와 stable_sort()의 차이를 알 수 있는 좋은 경험이었다. 만약 sort() 함수의 동일한 값에 대한 기존 순서를 유지하고 싶다면 인덱스 정보를 추가로 compare() 함수에 추가해준다면 될 것이다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll, int> mp;
ll n, c, temp;
vector<pair<ll, int>> cnt;
bool cmp(pair<ll, int> a, pair<ll, int> b) {
return a.second > b.second;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//입력
cin >> n >> c;
cnt.push_back({ 0, 0 }); // 1부터 탐색하기 위한 더미
//수행
for (int i = 0; i < n; i++) {
cin >> temp;
if (mp[temp] == 0) {//0은 더미
cnt.push_back({ temp, 1 }); //cnt에 숫자와 카운트 기록
mp[temp] = cnt.size() - 1; //mp에 해당 숫자 정보로 가는 cnt 인덱스 기록
}
else {
cnt[mp[temp]].second++; //map에서 해당 숫자의 인덱스를 찾고 cnt++
}
}
//정렬
stable_sort(cnt.begin(), cnt.end(), cmp);
//출력
for (int i = 0; i < cnt.size(); i++) {
for (int j = 0; j < cnt[i].second; j++) cout << cnt[i].first << " ";
}
return 0;
}'알고리즘 : C++ > BaekJoon' 카테고리의 다른 글
| 백준 15686번 - 치킨 배달 (0) | 2023.05.23 |
|---|---|
| 백준 4659번 - 비밀번호 발음하기 (0) | 2023.05.23 |
| 백준 2828번 - 사과 담기 게임 (0) | 2023.05.20 |
| 백준 1992번 - 쿼드트리 (0) | 2023.05.20 |
| 백준 2583번 - 영역 구하기 (0) | 2023.05.20 |