파이썬으로 구현하는 세포 융합 문제 완벽 가이드

문제 개요

여러 세포의 크기를 담고 있는 숫자 리스트 cells가 주어집니다. 각 반복 단계에서 가장 큰 두 세포 a와 b가 다음 규칙에 따라 상호작용합니다.

• 만약 a = b라면, 두 세포는 모두 소멸합니다.
• 그렇지 않으면 두 세포는 하나로 합쳐지며, 새로운 크기는 ((a + b) / 3)의 내림값(floor)이 됩니다.

이 과정을 반복한 후 마지막에 남은 세포의 크기를 구하고, 만약 남은 세포가 없다면 -1을 반환해야 합니다.

예시로 이해하기

입력이 [20, 40, 40, 30]이라면 결과는 16이 됩니다.

첫 번째 반복에서 크기가 40인 두 세포가 서로 같아 소멸하고, 이후 20과 30이 합쳐져 ((20 + 30) / 3)의 내림값인 16이 됩니다.

해결 접근 방법

이 문제는 매번 가장 큰 두 값을 빠르게 꺼내야 하므로 힙(Heap) 자료구조를 활용하는 것이 효율적입니다. 파이썬의 heapq 모듈은 기본적으로 최소 힙(min-heap)을 지원하기 때문에, 값들을 음수로 변환하여 최대 힙처럼 동작하도록 만드는 것이 핵심입니다.

알고리즘은 다음과 같이 진행됩니다.

1. cells 배열의 모든 값을 음수로 변환합니다.
2. 변환된 배열로 힙을 생성합니다(heapify).
3. 힙에 원소가 2개 이상 남아 있는 동안 다음을 반복합니다.
   • 두 개의 원소를 꺼내고 부호를 되돌려 first와 second에 저장합니다.
4. first와 second가 서로 다르면, ((first + second) / 3)의 내림값에 음수를 취해 힙에 다시 삽입합니다.
5. 반복이 끝난 후 힙에 원소가 남아 있으면 그 값의 부호를 되돌려 반환하고, 비어 있다면 -1을 반환합니다.

파이썬 구현 코드

from heapq import heapify, heappop, heappush

class Solution:
    def solve(self, cells):
        cells = [-x for x in cells]
        heapify(cells)
        while len(cells) > 1:
            first, second = -heappop(cells), -heappop(cells)
            if first != second:
                heappush(cells, -((first + second) // 3))
        return -cells[0] if cells else -1

ob = Solution()
cells = [20, 40, 40, 30]
print(ob.solve(cells))

입력

[20, 40, 40, 30]

출력

16

복잡도 분석

n개의 세포가 있을 때, 매 반복마다 힙 연산(삽입 및 삭제)은 O(log n)의 시간이 걸립니다. 최악의 경우 총 n-1번의 융합이 발생할 수 있으므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 힙 저장을 위해 O(n)입니다.