Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 숫자 하나를 지웠을 때 모든 빈도가 같아지는 최장 시퀀스 찾기

숫자로 이루어진 리스트가 주어졌을 때, 시퀀스에서 딱 하나의 숫자를 삭제했을 때 남은 모든 숫자의 등장 횟수가 서로 같아지는 가장 긴 시퀀스의 길이를 구하는 것이 이번 문제의 목표입니다.

예를 들어 입력이 numbers = [2, 4, 4, 7, 7, 6, 6]이라면 출력은 7입니다. 여기서 숫자 2는 한 번만 등장하므로 2를 완전히 제거하면 4, 7, 6이 각각 두 번씩 등장해 빈도가 완벽하게 일치하기 때문입니다.

문제 해결 접근 방법

핵심 아이디어는 배열을 왼쪽부터 순회하면서 매 시점의 빈도 상태를 추적하고, 현재까지 확인된 접두사(prefix)가 조건을 만족하는지 확인하는 것입니다. 이를 위해 세 가지 자료구조를 사용합니다.

  • num_freq — 각 숫자가 지금까지 몇 번 등장했는지 저장하는 맵
  • freq_freq — 빈도 값 자체의 분포, 즉 "특정 빈도를 가진 숫자가 몇 개인지"를 저장하는 맵
  • diff_freq — 현재 존재하는 서로 다른 빈도 값들을 담는 집합(set)

알고리즘 단계

  1. num_freq, freq_freq 맵과 diff_freq 집합을 초기화하고, 결과값 result를 1로 설정합니다.
  2. 배열의 각 인덱스 i와 값 num에 대해 다음을 반복합니다.
    • cur_freq에 현재 num의 기존 빈도를 저장한 뒤, num_freq[num]을 1 증가시킵니다.
    • freq_freq[cur_freq]는 1 감소시키고 freq_freq[cur_freq + 1]은 1 증가시켜 빈도 분포를 갱신합니다.
    • diff_freq에 cur_freq + 1을 추가하고, cur_freq가 집합에 있으면서 해당 빈도를 가진 숫자가 0개가 되었다면 집합에서 제거합니다.
    • diff_freq의 원소들로 리스트 df_list를 만듭니다.
    • 서로 다른 빈도가 1개뿐이라면 모든 숫자의 빈도가 이미 동일한 상태이므로 result = i + 1로 갱신합니다.
    • 서로 다른 빈도가 정확히 2개라면, 숫자 하나만 제거해서 균형을 맞출 수 있는지 추가로 검사합니다. 두 빈도 그룹 중 하나의 개수가 1이거나 개수 차이가 1이면서, 동시에 두 빈도 값의 차이가 1이거나 어느 한쪽 빈도 값이 1인 경우에만 result = i + 1로 갱신합니다.
  3. 순회가 끝나면 result를 반환합니다.

구현 예제

다음 코드를 통해 위 알고리즘이 실제로 어떻게 동작하는지 살펴보겠습니다.

from collections import defaultdict

class Solution:
    def solve(self, nums):
        num_freq = defaultdict(int)
        freq_freq = defaultdict(int)
        diff_freq = set()
        result = 1
        for i, num in enumerate(nums):
            cur_freq = num_freq[num]
            num_freq[num] += 1
            freq_freq[cur_freq] -= 1
            freq_freq[cur_freq + 1] += 1
            diff_freq.add(cur_freq + 1)
            if cur_freq in diff_freq and freq_freq[cur_freq] == 0:
                diff_freq.remove(cur_freq)
            df_list = list(diff_freq)
            if len(df_list) == 1:
                result = i + 1
            elif (
                len(df_list) == 2
                and any(
                    x == 1
                    for x in [
                        abs(freq_freq[df_list[0]] - freq_freq[df_list[1]]),
                        freq_freq[df_list[0]],
                        freq_freq[df_list[1]],
                    ]
                )
                and any(x == 1 for x in [abs(df_list[0] - df_list[1]), df_list[0], df_list[1]])
            ):
                result = i + 1
        return result

ob = Solution()
print(ob.solve([2, 4, 4, 7, 7, 6, 6]))

입력

numbers = [2, 4, 4, 7, 7, 6, 6]

출력

7

마무리

이 알고리즘은 입력 배열을 한 번만 순회하면서 매 단계마다 빈도 상태를 효율적으로 갱신하므로, 긴 입력에서도 좋은 성능을 보입니다. "빈도의 빈도"(freq_freq)와 "서로 다른 빈도의 집합"(diff_freq)을 함께 관리하면, 숫자 하나를 제거했을 때 빈도가 균형을 이루는지를 매 순간 빠르게 판단할 수 있다는 점이 핵심 포인트입니다.