알고리즘 :: 백준 :: 2910 - 빈도 정렬

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 요소 개수: 1 ≤ N ≤ 1,000
• 각 요소의 최댓값(상한): 1 ≤ C ≤ 1,000,000,000

✏️ 문제풀이

빈도 정렬의 기준은 '많이 등장한 순'으로, 등장횟수가 같다면 '앞서 등장한 순'입니다.

즉, 각 숫자와 대응하는 인덱스의 값마다 아래와 같은 정보를 갖고 있어야 합니다.

• 이 숫자가 몇 번 등장했는지
• 이 숫자가 언제 처음 등장했는지

로직은 다음과 같습니다.

1. 숫자를 입력받습니다. 등장횟수, 첫 등장 인덱스 번호 정보를 함께 저장합니다.
   
   • 처음 등장했다면, 등장횟수는 1 입니다.
   • 처음 등장한 숫자가 아니라면, 삽입하지 말고 등장횟수만 1 증가시킵니다.
2. 문제에 나온 빈도 정렬의 기준에 따라 정렬합니다.
   • 원하는대로 정렬시켜주는 STL 함수는 없기 때문에 따로 정렬 함수객체를 만들거나 람다함수를 만들면 됩니다.

어떤 컨테이너를 사용할지는 취향에 따라 다릅니다.

• `std::unordered_map<int, pair<int, int>>`로 한 번에 저장하기
  • 숫자 / 등장횟수 / 첫 등장 인덱스 세 가지 정보를 하나의 컨테이너로 모두 처리합니다.
  • 추후 정렬은 `std::vector`에서 이뤄지는데, 세 변수를 다루므로 `std::vector<tuple<int, int, int>>`를 사용하게 됩니다.
• `std::unordered_map<int, int>` 2개 사용하기
  • { 숫자 / 등장횟수 } 정보를 저장하는 컨테이너와 { 숫자 / 첫 등장 인덱스 } 정보를 저장하는 컨테이너를 따로따로 만듭니다.
  • 추후 정렬은 `std::vector`에서 이뤄지는데, { 숫자 / 첫 등장 인덱스 } 정보를 갖고있는 컨테이너가 따로 있기 때문에 우선 빈도 순으로만 정렬하기 위해 `std::vector<pair<int, int>>`를 사용하게 됩니다.

두 접근법 모두 장단이 있기 때문에 본인에게 편한 쪽으로 진행하면 됩니다.

📝 코드

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

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	int N, C;
	cin >> N >> C;
	// key: 입력받은 숫자, value: <등장횟수, 첫 등장 인덱스 번호>
	unordered_map<int, pair<int, int>> m;
	for (int i = 0; i < N; ++i) {
		int num;
		cin >> num;
		// 이미 값이 있다면, 등장횟수 1 증가 / 없다면 새로운 요소로 삽입
		if (m.find(num) != m.end()) m[num].first++;
		else m[num] = {1, i};
	}
	vector<tuple<int, int, int>> v;
	v.reserve(m.size());
	// map의 모든 요소를 vector에 넣는다.
	for (const auto& it : m)
		v.push_back({it.first, it.second.first, it.second.second});
	// 등장횟수에 대해 내림차순 + 첫 등장 인덱스 번호에 대해 오름차순
	sort(begin(v), end(v), [](const auto& lhs, const auto& rhs) {
		if (get<1>(lhs) == get<1>(rhs)) return get<2>(lhs) < get<2>(rhs);
		return get<1>(lhs) > get<1>(rhs);
	});
	// 모든 원소를 등장횟수만큼 반복해서 출력함.
	for (const auto& it : v)
		for (int i = 0; i < get<1>(it); ++i)
			cout << get<0>(it) << ' ';
}

 

🔗 코드 링크

🕧 결과