[TIL] 250629 - 정렬 기반 최빈값 탐색 패턴 2가지 비교

문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

 

입력

첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.

 

출력

첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.

 

예제 입력 1 

5
1
2
1
2
1

 

예제 출력 1 

1

 

예제 입력 2 

6
1
2
1
2
1
2

 

예제 출력 2 

1

 

 

 

핵심 아이디어

 

• 정렬된 값들을 순서대로 순회하면서, 같은 수가 연속되면 카운팅.
• max 값도 함께 기록해서 문제 정답 맞춰줌
• 총 2가지 방식으로 구현함. 첫번재는 deque사용, 2번째는 사용 X

 

1. deque를 활용해 반복적으로 앞에서 값을 빼며 탐색 → 큐 스타일 처리
   • 마지막 그룹 처리는 필수

n = int(input())
from collections import deque
arr = []
for _ in range(n):
    arr.append(int(input()))
arr.sort()
arr = deque(arr)

val = arr.popleft()
count = 1
max_count = 0
max_val = val
while arr:
    i = arr.popleft()
    if val == i:
        count += 1
        val = i
    else:
        if count>max_count:
            max_count = count
            max_val = val
        val = i
        count = 1
# 마지막 그룹 체크
if count > max_count:
    max_val = val
     
print(max_val)

 

 

 

 

    2. 정렬 + 인덱스 기반 연속 탐색

n = int(input())
arr = [int(input()) for _ in range(n)]

arr.sort()

cnt = 0
mxval = -(1 << 62)  # 아주 작은 수
mxcnt = 0

for i in range(n):
    if i == 0 or arr[i] == arr[i - 1]:
        cnt += 1
    else:
        if cnt > mxcnt:
            mxcnt = cnt
            mxval = arr[i - 1]
        cnt = 1  # 새로운 숫자 시작

# 마지막 숫자 그룹 체크
if cnt > mxcnt:
    mxval = arr[n - 1]

print(mxval)

• 정렬 후, 인접한 값 비교를 통해 최빈값 파악
• arr[i] == arr[i-1] 조건으로 그룹을 탐색하며 인덱스로 컨트롤

 

위 두 풀이는 아래와 같은 문제에 활용이 가능할 것 같습니다.

 

• 최빈값 탐색 (이번 문제처럼)
• 정렬 후 그룹 묶기
• 연속된 수 카운팅
• 같은 값의 최대 길이/구간 길이 탐색