[BOJ] 2910번 : 빈도 정렬

1. problem : 

https://www.acmicpc.net/problem/2910

 

 

2. solution 1 :

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

vector<tuple<int,int,int>> nums; // {숫자, 순서, 빈도} 초기값 {0,0,0}
int n, c; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> c;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		auto it = find_if(nums.begin(), nums.end(), [x](const tuple<int, int, int>& t) {
			return get<0>(t) == x;
			});
		if (it != nums.end()) {
			get<2>(*it)++; // 이미 vector에 존재하는 경우, 빈도만 증가 
		}
		else {
			nums.push_back(make_tuple(x,i,1)); // 없을경우, 숫자,순서,빈도=1로 초기화
		}
	}
	sort(nums.begin(), nums.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
		if (get<2>(a) != get<2>(b)) return get<2>(a) > get<2>(b); 
		return get<1>(a) < get<1>(b);
		});
	
	for (int i = 0; i < nums.size(); i++) {
		while (get<2>(nums[i])) {
			cout << get<0>(nums[i]) << ' '; 
			get<2>(nums[i])--;
		}
	}
}

find_if 함수를 배웠다. lambda 함수라고한다. capture부분에 target을 넣어주고, tuple의 특정원소가 target가 똑같은지, 비교해주는 함수이다. 만약 같은 값이 있다면, 그 부분의 iterator를 반환해주고, 없다면, end를 반환한다. 

 

3. solution 2 :

// Authored by : jihwan0123
// Co-authored by : -
// http://boj.kr/0fd334ddb06d417689cd6c944d5a0585
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
  return a.X > b.X;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, c;
  cin >> n >> c;
  vector<pair<int, int>> arr; // pair : {cnt, num}
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    bool chk = false;
    for (auto &a : arr) {
      if (a.Y == x) {
        chk = true;
        a.X++;
        break;
      }
    }
    if (!chk) arr.push_back({1, x});
  }
  stable_sort(arr.begin(), arr.end(), cmp);

  for (auto b : arr)
    while (b.X--) cout << b.Y << ' ';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0F/solutions/2910.cpp

basic-algo-lecture/0x0F/solutions/2910.cpp at master · encrypted-def/basic-algo-lecture