백준 2910 : 빈도 정렬

https://www.acmicpc.net/problem/2910

1. 접근

• 단순하게 sort 함수를 사용해서, 빈도가 더 높은 순서대로 정렬하면 된다.
• sort의 세번째 인자인 cmp함수에서 빈도와 첫번째 인덱스 값을 비교해주면 된다.
• 처음에 count를 숫자 값을 사용하는 vector로 사용했지만 메모리초과가 발생했다.
  => count도 map 에 저장해서 풀어주었다.
• 입력을 받을 때 count와 첫번째 인덱스 값을 넣어주고, 나중에 그 값을 이용해서 정렬해준다.

2. 나의 풀이

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

int n, c;
map<int, int> firstindex;
map<int,int > countarr;

bool cmp(int x,int y){
	if (x == y)	return false;
	if (countarr[x] > countarr[y])	return true;
	else if (countarr[x] == countarr[y]) {
		if (firstindex[x] >= firstindex[y])	return false;
		else return true;
	}
	else return false;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> input;
	cin >> n >> c;

	input.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> input[i];
		countarr[input[i]]++;
		if (firstindex.find(input[i]) == firstindex.end()) {
			firstindex[input[i]]= i;
		}
	}

	sort(input.begin(), input.end(), cmp);
	
	for (int i = 0; i < n; i++) {
		cout << input[i] << " ";
	}
	cout << "\n";
	return 0;
}