백준 2910 빈도 정렬, c++

 

 

 

코드 구현을 위한 대략적인 나의 로드맵은 다음과 같다.

3번에서 짝을 짓는 것을 구현하기 위해서는 해시 맵 key-value를 사용해야 했다.

 

 

 

구현한 코드는 다음과 같다.

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

int main() {
    //초기화
    int N, C;
    int arr[N];
    int num = 0;
    unordered_map<int, int> myHashMap = {{0,0}, };
    for (const auto& pair : myHashMap) {
        pair.first = num;
        num++;
    }
    
    // N, C 입력 받기
    cin >> N >> C;
    
    //1,2,3구현
    for(int i=0; i<N; i++){
        cin >> arr[i];
        myHashMap[arr[i]].second++;
    }
    
    //4구현, value에 따라 정렬
    vector<pair<int, int>> keyValueVector(myHashMap.begin(), myHashMap.end());
    sort(keyValueVector.begin(), keyValueVector.end(), [](const auto& lhs, const auto& rhs) {
        return lhs.second > rhs.second; // 큰 순서대로 정렬
    });
    
    //5구현
    for (const auto& pair : keyValueVector) {
        for(int i=0; i<pair.second; i++){
            cout << pair.first << " ";
        }
    }
    
    return 0;
}

하지만 오류가 났다. 문법 오류인 것 같아 수정이 필요했다.

 

 

 

최종 코드는 다음과 같다.

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

map <int, int> order; //index 저장
bool cmp(pair<int, int>& a, pair<int, int>& b){
	if (a.second == b.second)
		return order[a.first] < order[b.first]; //기존의 순서 지키기
	return a.second > b.second;
}

int main() {
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    //N, C 입력받기
	int N, C;
	cin >> N >> C;

    // 해시함수(배열) 입력받기
	map<int, int> m;
	int num; //배열 값 하나씩 입력받기
	for (int i = 0; i < N; i++) {
		cin >> num;
		m[num]++;
		if (order[num] == 0)
			order[num] = i+1;
	}
	
    //value 오름차순 정렬
	vector<pair<int, int>> vec(m.begin(), m.end());
	sort(vec.begin(), vec.end(), cmp);

    // 순서대로 출력
	for (auto x : vec) {
		for (int i = 0; i < x.second; i++) {
			cout << x.first << " ";
		}
	}

	return 0;
}

+ cmp는 a, b 배열 안의 두 값을 비교해서 true, false로 반환해 value에 따라 자리를 바꿔줄 지 결정하는 함수

정렬하면서 키값이 이동해 기존 키값을 잃어버리게 되는 상황 방지.