2910 - 빈도 정렬

문제

코드

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> v;
map<int, int> mp, mp_first;
int n,c,a[1004];

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

int main(){
	cin >> n >> c;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		mp[a[i]]++;
		if(mp_first[a[i]] == 0){
			mp_first[a[i]] = i + 1;
		}
	}
	
	for(auto it : mp){
		v.push_back({it.second, it.first});
	}
	
	sort(v.begin(), v.end(), cmp);
	
	for(auto i : v){
		for(int j = 0; j < i.first; j++){
		cout << i.second << " ";
	}
}
	
	return 0;
}

해설

마지막 출력할 때 for(auto it : v) it.second만 하면 그냥 순서대로만 나오니까 원하는 출력 값에 맞추려면 반복수만큼 반복해줘야한다.

결과

후기

쉽다고 생각했다. 배열로 접근을 했지만 10억이라는 최댓값을 줘서 오버플로가 났다.
그래서 map과 vector를 사용했다.
둘의 정확한 용도의 차이점은 모르겠으나 느낌상 이번 문제에서는 sort를 해야해서 vector를 쓰지 않았나 싶다.
런타임 에러는 문제의 배열 제한 1000을 100으로 잘못봤다.
뭔가 힌트없이 해낼 수 있을거라 생각했는데 조금 아쉽다.