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

문제

 

문제 분석

- 먼저 C의 값이 높다. 이 점을 유념해서 봐야한다. (단, 자료형은 int 형을 사용해도 된다. 21억을 넘진 않기 때문이다.)

[방법1]

자료를 저장할 때 배열의 인덱스로 접근하는 방식으로 문제를 해결한다면 메모리 초과가 날 것이다.

=> 왜냐하면 배열은 먼저 메모리에 할당을 해야 값을 넣을 수 있기 때문이다.

 

[방법2]

이런 문제를 해결하기 위해 insert가 될 때마다 메모리에 할당하는 map 자료구조를 사용하면 메세지의 최대 길이는 1000이므로 메모리 문제가 해결된다. 그러나 map/set과 같은 해시 자료구조는 넣은 순서대로 저장되지 않는다. (vector, tuple, pair의 자료구조는 넣은 순서대로 저장된다.)

 

[방법3]

방법1과 방법2에서 도출되었던 문제를 바탕으로 메모리 초과 문제와 들어오는 순서대로 저장하기 위해 가변 배열(vector 자료구조)을 사용하고 동시에 숫자와 숫자에 따른 빈도수 데이터가 필요하므로 pair 자료구조를 사용한다. 

vector<pair<int,int>> v;

정답 코드

- 이미 한 번 나왔던 숫자인지 검사하고 처음 나오는 숫자이면 vector에 데이터를 추가하고, 기존에 나온 숫자면 second값(빈도)을 1 증가 시켜준다.

- 문제에서 나온대로 정렬 커스텀마이징을 통해 구현하면 된다.

- 정렬 커스텀마이징 할 때 return false; 는 정렬을 하지 않는다는 것을 의미한다.

- stable_sort는 vector에 저장되어 있는 순서를 보장하여 조건에 맞게 정렬한다는 의미이다. 

// 수의 범위가 1,000,000,000 이므로 21억을 넘지는 않는다. 

// 배열의 인덱스로 접근하는 방식으로 문제를 해결한다면 메모리 초과가 날 것이다.
// => 1,000,000,000을 만들어야 하므로

// map 을 사용하면, 먼저 입력받은 순서를 알기 어렵다. (해시는 insert 한 순서대로 저장이 되는 것이 아니다. 저장되는 순서는 랜덤이다.)

// vector<pair<int,int>> 을 사용한다. (들어오는 순서도 알 수 있고, 숫자 빈도수도 셀 수 있다.)


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

vector<pair<int, int>> v; // (숫자, 횟수)

// 1순위 ) 수의 빈도수대로 내림차순
// 2순위 ) 먼저 나온 순
bool cmp(const pair<int, int> p1, const pair<int, int> p2) {
	if (p1.second != p2.second) return p1.second > p2.second;
	
	return false; // 정렬을 하지 않음.
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int N, C;
	cin >> N >> C;
	
	for (int i = 0; i < N; i++) {
		int input_num;
		bool flag = true; // 한 번도 안나오면 true
		cin >> input_num;
		// 이미 한 번 나왔던 숫자인지 검사
		for (int j = 0; j < v.size(); j++) {
			if (v[j].first == input_num) {
				flag = false;
				v[j].second++;
			}
		}

		// 한 번도 나오지 않은 새로운 숫자라면 vector에 push
		if (flag == true)
			v.push_back(make_pair(input_num, 1));
	}

	stable_sort(v.begin(), v.end(), cmp); //vector에 저장된 순서를 보장해야 한다.

	// 출력
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v[i].second; j++) {
			cout << v[i].first << " ";
		}
	}
	return 0;
}

교훈점

- stable_sort는 자료구조(vector)에 담겨있는 데이터의 순서를 보장하여 정렬한다.

즉, 정렬의 순위가 같으면 먼저 입력된 것이 우선 순위로 정렬된다.

 

- map/set과 같은 해시 자료구조는 데이터의 입력을 저장할 때 넣은 순서를 보장하지 않는다. 입력된 데이터가 저장되는 순서는 랜덤한 순서로 저장된다.