파이썬(Python)으로 최대 빈도 요소와 동일한 빈도를 가지는 가장 짧은 부분 리스트 길이 찾기

문제 개요

숫자로 이루어진 리스트 nums가 주어졌다고 가정해 보겠습니다. 이 리스트에서 가장 자주 등장하는 숫자의 빈도를 k라고 할 때, 우리가 구해야 하는 것은 부분 리스트(sublist) 안에서 가장 빈번한 요소의 빈도 역시 k가 되는 가장 짧은 부분 리스트의 길이입니다.

문제 예시

예를 들어 입력이 nums = [10, 20, 30, 40, 30, 10]이라면 결과는 3이 됩니다. 이 리스트에서 가장 많이 등장하는 숫자는 10과 30이며, 각각 두 번씩 나타나므로 k = 2입니다. 여기서 [30, 40, 30]이라는 부분 리스트를 선택하면 30이 포함되면서 그 빈도도 2가 되는, 즉 조건을 만족하는 가장 짧은 구간이 되기 때문입니다.

풀이 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

L := nums의 길이
rnums := nums를 뒤집은 리스트
d := nums에 포함된 각 요소의 빈도수를 저장한 맵(딕셔너리)
mx := d의 모든 값 중 최댓값
vs := d에서 빈도가 mx와 같은 키(k)들의 리스트
mn := L로 초기화
vs의 각 v에 대해 다음을 수행합니다.
- mn := mn과 (L − (rnums에서 v의 인덱스) − (nums에서 v의 인덱스)) 중 작은 값
mn 반환

동작 원리

핵심 아이디어는 간단합니다. 어떤 최대 빈도 숫자 v에 대해, v가 처음 등장하는 위치와 마지막으로 등장하는 위치 사이의 구간이 곧 "v의 모든 등장 횟수를 포함하는 가장 짧은 부분 리스트"가 됩니다. 리스트를 뒤집은 rnums에서의 인덱스를 활용하면 마지막 등장 위치를 손쉽게 계산할 수 있고, 전체 길이 L과 조합하여 해당 구간의 길이를 구할 수 있습니다. 모든 후보 숫자에 대해 이 값을 계산한 뒤 최솟값을 선택하면 정답을 얻을 수 있습니다.

구현 예제

아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.

from collections import Counter

def solve(nums):
    L = len(nums)
    rnums = nums[::-1]

    d = Counter(nums)
    mx = max(d.values())
    vs = [k for k in d if d[k] == mx]

    mn = L
    for v in vs:
        mn = min(mn, (L - rnums.index(v)) - nums.index(v))
    return mn

nums = [10, 20, 30, 40, 30, 10]
print(solve(nums))

입력

[10, 20, 30, 40, 30, 10]