[백준] 2910. 빈도정렬 (C++)

Level

Silver3

 

Idea

입력값, 입력값의 빈도, 입력값의 순서를 모두 저장할 수 있는 방법을 생각해야한다. 나는 두개의 map을 이용해서 mp1에는 빈도, mp2에는 입력 순서를 저장하는 방법으로 문제를 풀었다.

이 방법을 찾기까지의 여정을 기록해봤다...

처음엔 단순무식하게 map에 입력값을 key로 넣고 빈도, 입력값을 value로 넣는 방법을 생각했다. map은 기본적으로 하나의 키에 하나의 값을 넣는 걸로 설정되어있으므로.. 이렇게 풀면 상당히 복잡해지고 힘들다. 그래서 map을 버리고 벡터를 써봤다. 빈도와 입력 순서를 기준으로 정렬하므로 여기서 map의 자동정렬 기능은 전혀 유용하지 않았다. 그래서 굳이 map을 써야하는 이유를 모르겠어서 tuple_vector 로 바꿨다. 그런데 벡터는 a[b]++ 같은 연산이 안 됐다. 그리고 튜플 벡터는 접근 방법도 복잡해서 다시 map으로 돌아왔다.

 

 

Key Point

map은 기본적으로 key를 기준으로 정렬된다.  value를 기준으로 정렬하려면 vector에 map을 옮기는 방법으로 정렬해야한다. 코테에서 이 방법이 기억이 안나면 낭패이므로 외워두는게 좋을듯하다.

 

 

Code

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

map<int, int>mp;
map<int, int>mp_ord;

bool cmp(pair<int, int>a, pair<int, int>b) {
	if (a.second == b.second) {
		return mp_ord[a.first] < mp_ord[b.first];
	}
	return a.second > b.second;
}

int main() {

	int n = 0, c = 0;
	int input = 0;
	
	

	cin >> n >>c;

	for (int i = 0; i < n; i++) {
		cin >> input;
		
		if (mp.find(input) == mp.end()) {
			mp.insert({ input,1 });
			mp_ord.insert({ input, i });
		}
		else {
			mp[input]++;
		}
	}

	vector<pair<int, int>>v(mp.begin(),mp.end());

	sort(v.begin(), v.end(), cmp);

	for (auto a : v) {
		for (int i = 0; i < a.second; i++) {
			cout << a.first << endl;
		}
	}


	return 0;
}

 

---

 

그리고 약간의 자기 반성의 시간

나는 언제나 '짧은 코드', '최대한 하나로 해결하는 코드' 에 강박이 있는 것 같다. 저렇게 한다고 좋은 코드가 나오는 것도 아닌데... 최대한 많은 문제를 풀어보며 생각을 넓히려고 노력하고 있다. 맵, 벡터를 하나만 쓰라고 정해진 것도 아닌데 꼭 하나로 해결하려다가 쉬운 문제도 어렵게 접근했다. 오늘도 이렇게 반성을 한다...