파이썬으로 중첩 리스트 평탄화 반복자(Nested Iterator) 구현하기

중첩 리스트 평탄화 문제란?

정수들이 중첩된 형태의 리스트가 주어졌다고 가정해 보겠습니다. 각 요소는 정수이거나 리스트일 수 있으며, 그 리스트 안의 요소 역시 정수 또는 또 다른 리스트일 수 있습니다. 우리의 목표는 이러한 중첩 구조를 순회할 수 있는 반복자(iterator)를 구현해 모든 정수를 일렬로 펼쳐내는 것입니다.

예를 들어 입력이 [[1, 1], 2, [1, 1]]이라면, 출력은 [1, 1, 2, 1, 1]이 되어야 합니다.

해결 접근 방법

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

초기화(__init__): 중첩 리스트를 입력받아 내부 상태를 설정합니다. 결과를 담을 빈 리스트 res와 인덱스 변수 index := 0을 만들고, 곧바로 getVal() 메서드를 호출합니다.
getVal(): 재귀적으로 동작하는 핵심 함수입니다. 리스트의 각 요소를 순회하면서, 요소가 정수이면 res 배열에 추가하고, 리스트라면 다시 getVal()을 호출해 더 깊은 계층까지 탐색합니다.
next(): 현재 index가 가리키는 값을 반환한 뒤, index를 1 증가시킵니다.
hasNext(): 아직 반환하지 않은 요소가 남아 있다면 True를, 더 이상 없다면 False를 반환합니다.

Python 구현 예제

아래 코드를 통해 실제 구현 과정을 자세히 살펴보겠습니다.

class NestedIterator(object):
    def __init__(self, nestedList):
        self.res = []
        self.index = 0
        self.getVal(nestedList)

    def getVal(self, NestedList):
        for item in NestedList:
            if isinstance(item, int):
                self.res.append(item)
            else:
                self.getVal(item)

    def next(self):
        self.index += 1
        return self.res[self.index - 1]

    def hasNext(self):
        if self.index == len(self.res):
            return False
        return True

ob = NestedIterator([[1,1],2,[1,1]])
while ob.hasNext():
    print(ob.next())

입력

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

출력

동작 원리 및 성능 분석

이 구현은 초기화 단계에서 재귀 함수 getVal()을 통해 중첩 리스트 전체를 한 번 순회하며 모든 정수를 res 리스트에 미리 저장합니다. 그런 다음 next()와 hasNext()는 저장된 리스트를 인덱스 기반으로 조회하기 때문에 매우 빠르게 동작합니다.

시간 복잡도 측면에서 보면, 초기화 시 전체 요소 수를 N이라 할 때 O(N)의 비용이 들며, 이후 next()와 hasNext() 호출은 각각 O(1)입니다. 따라서 반복자를 통해 데이터를 여러 차례 소비해야 하는 상황에서도 효율적인 구조라고 할 수 있습니다.