JArchive 프로그래밍 일기

문제

빈도 정렬 백준 2910

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, c, num;
map<int,int> idxm; // {숫자, 처음 나온 인덱스} 저장
map<int,int> recentm; // {숫자, 빈도} 저장
vector<pair<int,int>> v;

bool cmp(pair<int,int> a, pair<int,int> b){ // 빈도 내림차순, 인덱스 오름차순
  if(a.X == b.X) return idxm[a.Y] < idxm[b.Y];
  return a.X > b.X;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> c;
  for(int i = 0; i < n; i++){
    cin >> num;
    recentm[num]++; // num의 빈도를 1 증가시킨다
    if(idxm[num] == 0 ){ // num이 처음 나왔다면, 인덱스를 저장한다.
      idxm[num] = i+1;
    }
  }

  // recentm {숫자, 빈도} -> {빈도, 숫자} 로 바꿔서 벡터에 저장
  for(auto & it : recentm){
    v.emplace_back(it.Y, it.X);
  }

  // 빈도를 기준으로 정렬하되, 인덱스 조건 고려하여 정렬하도록 cmp 함수 적용
  sort(v.begin(), v.end(), cmp);

  for(int i = 0; i < v.size(); i++){ // 숫자의 빈도(== v[i].X)만큼 숫자를 출력.
    for(int j = 0; j < v[i].X; j++){
      cout << v[i].Y << ' ';
    }
  }
  return 0;
}

리뷰

처음에는 벡터만을 생각해서 풀어서 감이 안오고 어렵게 느껴졌다.
key의 중복을 허용하지 않는 map을 이용해서 풀었다.

처음에 입력 받을 때 2개의 맵을 초기화한다.
(숫자, 빈도)를 저장하는 recentm map에 빈도를 저장한다.
(숫자, 숫자가 처음 나온 인덱스)를 저장하는 idxm map에 '숫자가 처음 등장한 인덱스'를 저장한다.

인덱스가 0이면 '처음 나왔다' 고 보기 때문에. 1+i를 인덱스로 저장했다.

빈도가 가장 많은 숫자가 앞에 와야 하니까 정렬이 필요하다.
map recentm {숫자, 빈도} 을 vector v {빈도, 숫자}로 바꿔서 저장한다.

여기서 vector.emplace_back()을 썼는데. vector.push_back()과 동일한 기능이다.

push_back() 과 달리 emplace_back()는 데이터를 삽입할 때 임시 객체를 생성하지 않아서 약간 더 빠르다고 한다.

빈도가 같은 경우에, '숫자가 처음 등장한 인덱스'가 작은것을 우선하라는 조건을 주기 위해 cmp 비교 함수를 넣고 sort() 한다.

정렬이 끝나면, 숫자를 '숫자의 빈도'만큼 출력해주면 되니까 이중 반복문으로 vector 를 순회하여 출력한다.

iterator로 순회하는 반복문 코드 2가지 형태를 배웠다.

  map<int,int> recentm; // {숫자, 빈도} 저장

  // 아래 2개 반복문은 똑같이 동작한다. 
  for(auto & it : recentm)

  for(auto it = recentm.begin(); it != recentm.end(); it++) 
}