map과 vector를 효율적으로 잘 쓰고 sort() 사용시 사용자 정의 비교함수 cmp로 비교를 진행하는 문제이다.
수의 등장 횟수를 세야하므로 카운팅 배열을 사용하면된다.
그러나 공간제한이 128mb로 int cnt[100000000] 하면 약 4억 바이트 쓰게되고, 공간복잡도를 초과해버린다.
따라서 map에 key:숫자, value:등장횟수 형태로 출현 빈도를 카운팅하는게 적절하다.
(map은 탐색,접근,삽입,삭제의 시간 복잡도가 O(logn))이다
mp1에는key:수, value:출현 빈도mp2에는 mp2.insert({key,value})를 활용해 덮어쓰지않도록key:수, value:등장횟수
를 저장한다.
이후 sort() 사용을위해 vector에 mp1값을 복사해준다.
사용자 정의 함수로 등장 횟수 더 많은 애가 앞에 오도록, 그리고 등장 횟수 동일한 경우는 mp2에 접근해서 순서 확인해서 더 빨리 출현한애가 앞에오도록 정렬해준다.
이후 벡터를 순회하며 등장 횟수만큼 해당하는 수를 출력해준다.
시간복잡도는 처음에 mp1,mp2 초기화 과정에서 O(nlogn) , sort() 사용 과정에서 .. 비교횟수 O(mlogm), 각 비교에서 map에 접근하니 O(logm) -> O(mlogm*logm)
전체 시간 복잡도는 O(nlogn + mlogm*logm) 으로 연산량 따져보면 1억보다 매우 작아서 시간복잡도 측면에서도 안전하다
1. 풀이
#include <bits/stdc++.h>
using namespace std;
int n,c,tmp;
map<int,int> mp1,mp2;
vector<pair<int,int>> v;
bool cmp(pair<int,int> p1, pair<int,int>p2) {
if(p1.second == p2.second) {
return mp2[p1.first] < mp2[p2.first];
}
return p1.second > p2.second;
}
int main() {
cin >> n >> c;
for(int i=0;i<n;i++) { //O(nlogn)
cin >> tmp;
mp1[tmp]++;
mp2.insert({tmp, i});
}
for(auto it:mp1) { //O(M)
v.push_back({it.first, it.second});
}
sort(v.begin(),v.end(), cmp); //O(MlogM)
for(auto it : v) { //O(n)
for(int i=0;i<it.second;i++) {
cout << it.first << " ";
}
}
return 0;
}2. 오답노트
(1) map.insert({key, value})
map 의 삽입 방법은 map[key]=value; 도 있고 map.insert({key, value}); 도 있다.
전자는 덮어쓰기를 허용하고, 후자는 덮어쓰기를 허용하지 않는다.
나는 덮어쓰기를 허용하지 않는 후자의 방식을 사용했어야했는데, 문법이 잘 기억나지 않았다.
그래서 관련해서 이전에 정리해놨던 문법 글을 보고 코드를 작성했다.
C++의 pair든, 배열이든, vector든, map 이든 모두 중괄호
{}를 이용해서 요소를 나타냄을 잊지말자.
(2) map은 균형 이진 트리 -> 삽입, 탐색, 접근, 삭제 모두 O(logn)
map은 균형 이진 트리 로 구현된다.
그래서 삽입, 탐색, 접근, 삭제 모두
O(logn)의 시간 복잡도를 가진다.
이를 잊고 O(nlogn)이라 생각하여 이전에 옳은 출력이 나오는 풀이를 떠올렸는데 시간 복잡도 때문에 엎어버렸다.
map의 삽입, 탐색, 접근, 삭제의 시간 복잡도가 O(logn)임을 잘 기억해두자.
(3) map 여러개 써도 시간 복잡도 측면에서 문제없다
앞서 언급했듯이 map의 삽입, 탐색, 접근, 삭제의 시간 복잡도가 O(logn)이라. 이 문제처럼 mp1,mp2이렇게 많이 써도 시간복잡도 측면에서 문제를 일으킬 확률은 적다.
이렇게
카운팅이 필요한 문제에서std::map을 여러개써도 되니 적극적으로 활용하자.
(4) 사용자 정의 비교 함수 cmp로 sort() 를 이용해 정렬하기
처음에 내가 cmp정의하고 sort() 쓰는법이 잘 기억이 안났다. 특히 sort()의 마지막 인자로 cmp()를 전달해야하는지 cmp를 전달해야하는지 잘 떠오르지 않았다.
또한 cmp를 정의하는 형식이 잘 떠오르지 않았다.
vector<pair<int,int>> v;
bool cmp(pair<int,int> p1, pair<int,int>p2) {
if(p1.second == p2.second) {
return mp2[p1.first] < mp2[p2.first];
}
return p1.second > p2.second;
}cmp는 위와 같이 정의하면된다.
- 반환 타입 : bool
- 매개변수 : sort() 적용하는 vector 또는 배열의 요소의 type
- 앞 매개 변수 : 앞에꺼
- 뒷 매개 변수 : 뒤에꺼
sort()의 동작 : nlogn번 비교를 수행하며, 매 비교마다 cmp() 호출해서 1을 반환하도록 정렬한다.
