BOJ 5489 - Numbers

문제

N개의 정수가 주어질 때, 가장 많이 등장하는 수를 출력한다. 가장 많이 등장하는 수가 여러 개라면 그 중 가장 작은 수를 출력한다.

입력

첫째 줄에 정수의 개수 N이 주어진다. 둘째 줄에 N개의 정수가 주어진다.

출력

가장 많이 등장하는 수를 출력한다. 빈도가 같다면 가장 작은 수를 출력한다.

예제

입력	출력
`5` `3 1 2 1 3`	`1`

풀이

N개의 정수 중 빈도수가 가장 높은 수를 구하되, 빈도가 같을 경우 가장 작은 수를 선택한다.

map<int, int>로 각 수의 등장 횟수를 센다.
map은 키를 오름차순으로 저장하므로, 순서대로 순회하면서 최대 빈도를 갱신한다.
현재 수의 빈도가 최대 빈도보다 크면 최대 빈도와 정답을 갱신한다.
빈도가 같을 경우 이미 더 작은 수가 먼저 처리되었으므로 별도 처리가 필요 없다.

핵심 아이디어: map의 오름차순 순회 특성을 이용하면, 빈도가 같을 때 자동으로 더 작은 수가 우선순위를 가진다.

코드

#include <iostream>
#include <map>
using namespace std;
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int N;
  cin >> N;
 
  map<int, int> freq;
  for (int i = 0; i < N; i++)
  {
    int x;
    cin >> x;
    freq[x]++;
  }
 
  int maxCount = 0;
  int answer = 10001;
 
  for (auto &p : freq)
  {
    int number = p.first;
    int count = p.second;
 
    if (count > maxCount)
    {
      maxCount = count;
      answer = number;
    }
    else if (count == maxCount && number < answer)
    {
      answer = number;
    }
  }
 
  cout << answer << "\n";
  return 0;
}

복잡도

시간: O(N log N) — map 삽입 및 순회
공간: O(N) — 최대 N개의 서로 다른 키 저장

문제