문제 81
가장 많이 나온 수
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.
수열에서 가장 많이 등장하는 정수를 구하라. 그러한 정수가 여러 개라면 그중 가장 작은 정수를 구하라.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 100)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 100)$
출력
첫 번째 줄에 수열에서 가장 많이 등장하는 정수 중 가장 작은 정수를 출력한다.
예제 입력 1
6 3 1 2 3 1 2
예제 출력 1
1
예제 입력 2
5 1 2 2 3 2
예제 출력 2
2
공식 해설
값의 범위가 $1$부터 $100$까지이므로 빈도 배열에 각 수의 등장 횟수를 센다.
입력을 모두 읽으면 $1$부터 $100$까지 작은 수부터 확인한다. 현재 답보다 등장 횟수가 더 많은 수를 찾았을 때만 답을 바꾼다. 횟수가 같을 때는 먼저 선택된 더 작은 수를 유지하므로 동률 조건도 만족한다.
시간복잡도는 $O(N+100)$이다. 빈도 배열의 크기가 고정되어 있으므로 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
int count[101] = {};로 빈도를 센다. 값 $1$부터 $100$까지 순회하며 지금까지의 최대 빈도보다 엄격히 클 때만 답을 바꾼다. >=로 갱신하면 동률일 때 더 큰 값을 선택하게 된다.
C 구현
int count[101]에 빈도를 센다. 1부터 100까지 순회하면서 현재 최고 빈도보다 엄격히 클 때만 답을 바꾸면 동률에서 작은 수가 남는다.
Python 구현
길이 101의 빈도 리스트를 사용한다. 오름차순으로 순회하고 count[x] > best일 때만 갱신한다. Counter 전체를 정렬하거나 빈도용 클래스를 만들 필요는 없다.
Java 구현
int[101] 빈도 배열과 답·최대 빈도 변수만 둔다. 오름차순에서 엄격한 > 비교로 갱신하면 동률 처리도 함께 해결된다.
Rust 구현
[usize;101] 빈도 배열로 충분하다. 오름차순으로 돌며 현재 최고 빈도를 넘을 때만 답을 바꾼다. HashMap이나 sort는 필요 없다.
JavaScript 구현
길이 $101$의 Int32Array로 빈도를 세고, $1$부터 $100$까지 순회한다. 현재 최대 빈도보다 엄격히 클 때만 답을 바꾸면 동률에서 작은 수가 유지된다.
let answer = 1;
for (let x = 2; x <= 100; x++)
if (count[x] > count[answer]) answer = x;
console.log(answer);$N\le100$이므로 빈도는 작은 정수이고 모든 값을 정렬하거나 별도 해시 맵을 만들 필요가 없다.