파이썬으로 배우는 중첩 리스트 가중치 합계 II – 역방향 깊이 가중치 알고리즘

문제 소개

정수로 구성된 중첩 리스트(nested list)가 주어질 때, 리스트 안의 모든 정수를 각자의 깊이에 맞는 가중치로 곱한 뒤 합산한 값을 반환하는 문제입니다. 여기서 각 요소는 정수이거나 리스트일 수 있으며, 리스트 내부의 요소 역시 정수 또는 또 다른 리스트일 수 있습니다.

앞선 문제(중첩 목록 가중치 합계 I)에서는 루트에서 리프로 내려갈수록 가중치가 커지는 방식이었다면, 이번 문제는 정반대로 아래에서 위로(bottom-up) 가중치를 매깁니다. 즉, 가장 안쪽 레벨(리프)의 정수는 가중치 1을 가지며, 가장 바깥쪽 레벨(루트)의 정수가 가장 큰 가중치를 갖습니다.

예를 들어 입력이 [[1,1],2,[1,1]]인 경우 출력은 8입니다. 네 개의 1은 가장 안쪽 깊이에 위치해 각각 가중치 1을 받고, 하나의 2는 바깥쪽 깊이에 위치해 가중치 2를 받습니다. 따라서 (1×4) + (2×2) = 8이 됩니다.

해결 접근 방법

핵심 아이디어는 중첩 리스트를 한 번 순회하면서 각 정수의 값과 깊이를 함께 기록한 뒤, 최대 깊이를 기준으로 가중치를 역산하는 것입니다. 단계별로 살펴보면 다음과 같습니다.

depthSumInverse() 함수를 정의하고 중첩 리스트 nestedList를 인자로 받습니다.
(정수, 깊이) 쌍을 저장할 리스트 flats를 생성하고, 최대 깊이를 추적할 변수 maxd를 0으로 초기화합니다.
재귀 함수 flatten(nlst, dist)를 정의합니다. 호출될 때마다 깊이를 1 증가시키고 maxd를 갱신하며, 각 노드를 검사해 정수이면 (노드, 깊이)를 flats에 추가하고, 리스트이면 같은 함수를 재귀적으로 호출합니다.
flatten(nestedList, 0)을 호출해 전체 리스트를 평탄화(flatten)합니다.
flats에 담긴 각 (값 v, 깊이 d)에 대해 v × (maxd + 1 − d)를 계산해 누적합니다. 이 식은 가장 깊은 원소에는 가중치 1을, 루트에 가까운 원소에는 큰 가중치를 부여합니다.
누적된 합계 summ을 반환합니다.

구현 예제

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

class Solution(object):
    def depthSumInverse(self, nestedList):
        flats=[]
        self.maxd=0
        def flatten(nlst,dist):
            if isinstance(nlst,list):
                nlst=nlst
            dist+=1
            self.maxd=max(self.maxd,dist)
            for node in nlst:
                if isinstance(node,int):
                    flats.append((node,dist))
                else:
                    flatten(node,dist)
        flatten(nestedList,0)
        summ=0
        for v,d in flats:
            summ+=v*(self.maxd+1-d)
        return summ

ob = Solution()
print(ob.depthSumInverse([[1,1],2,[1,1]]))

입력

[[1,1],2,[1,1]]

출력

복잡도 분석

시간 복잡도는 중첩 리스트의 모든 요소를 정확히 한 번씩 방문하므로 O(N)입니다(단, N은 전체 정수와 리스트 요소의 총 개수). 공간 복잡도 역시 모든 (값, 깊이) 쌍을 flats에 저장해야 하므로 O(N)입니다.