백준 2910 빈도정렬 ) c++

실버 3이라고 만만하게 보고 풀었다가 접근 방식을 세번정도 갈아엎은 문제

 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

struct bindo {
	int num;
	int cnt;
	int idx;
};

vector<bindo> vec;

bool cmp(const bindo& b1,const bindo& b2) {
	if(b1.cnt == b2.cnt) {
		return b1.idx < b2.idx;
	}
	else {
		return b1.cnt > b2.cnt;
	}
}

int main(void)
{
	int n,c;
	cin >> n >> c;
	
	vector<int> rem;
	for(int i=0; i<n; i++) {
		int tmp;
		cin >> tmp;
		rem.push_back(tmp);
	}
	
	for(int i=n-1; i>=0; i--) {
		bool c = true;
		for(int j=0; j<vec.size(); j++) {
			if(vec[j].num == rem[i]) {
				c = false;
				vec[j].cnt += 1;
				vec[j].idx = i;
				break;
			}
		}
		
		if(c) {
			vec.push_back({rem[i],1,i});
		}
	}
	
	sort(vec.begin(),vec.end(),cmp);
	
	for(int i=0; i<vec.size(); i++) {
		for(int j=0; j<vec[i].cnt; j++) {
			cout << vec[i].num << " ";
		}
	}
	
	return 0;
}

 

정답이 나오긴 했지만 이렇게 하면 

N이 10000이 되는 경우 O(n2) = 1억 이므로 나와서 시간복잡도에 걸릴 확률이 매우 높아집니다.

 

그래서 map을 이용해야한다는걸 알고는 있었지만 정렬을 어떻게 할지 몰라서 다른 사람의 풀이를 참고했습니다.

 

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

map<int,int> order;

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

int main(void)
{
	int n,c;
	cin >> n >> c;
	map<int,int> ma;
	map<int,int>:: iterator it;
	vector<pair<int,int> > vec;
	
	for(int i=0; i<n; i++) {
		int tmp;
		cin >> tmp;
		ma[tmp]++;
		if(order[tmp] == 0) order[tmp] = i+1;
	}
	
	for(it = ma.begin(); it!= ma.end(); it++) {
		vec.push_back({it->first,it->second});
	}
	
	sort(vec.begin(),vec.end(),cmp);
	
	for(int i=0; i<vec.size(); i++) {
		for(int j=0; j<vec[i].second; j++) {
			cout << vec[i].first << " ";
		}
	}

	return 0;
}

위 코드처럼 하게되면 n이 10000개가 되어도 시간초과에 걸리지않습니다.

 

 

**

map 순회방법

map<int,int>:: iterator it;
for(it = ma.begin(); it!= ma.end(); it++) {
    vec.push_back({it->first,it->second});
}

 

 

map 두개를 이용해 sort 하는 것에 대해 잘 알아두자!

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