LeetCode | 341. Flatten Nested List Iterator

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

NestedIterator(List nestedList) Initializes the iterator with the nested list nestedList.
int next() Returns the next integer in the nested list.
boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.
Your code will be tested with the following pseudocode:

initialize iterator with nestedList

while iterator.hasNext()
    append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Constraints:

1 <= nestedList.length <= 500
The values of the integers in the nested list is in the range [-106, 106].

python 코드

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.q = []
        self.flatten(nestedList)

    def flatten(self, nl):
        for i in nl:
            if i.isInteger():
                self.q.append(i.getInteger())

            else:
                self.flatten(i.getList())

    def next(self) -> int:
        return self.q.pop(0)

    def hasNext(self) -> bool:
        return True if self.q else False

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

풀이

중첩 리스트를 눈에 보이는 순서 그대로 flat한 리스트로 옮기는 문제이다.

Nested List를 Flatten List로 바꾸는 방법은 여러가지가 있다. python 모듈 중 itertools를 사용하여 풀이할 수 있다. 여기에서 잘 설명이 되어있다. 이 블로그 글 중에 신박한 방법이 있어서 하나만 소개하자면

sum 함수를 사용하여 이중 리스트를 1차원 리스트로 변환할 수 있다.

>>> a = [[1,2],[3,4]]

일 때

>>> sum(a, [])
[1, 2, 3, 4]

라는 결과가 나오게 된다(와우)
sum함수는 sum(iterable, start=0) 이런 식으로 파라미터가 구성되어 있다. 따라서 sum(a)라고 하게 되면 디폴트로 더하는 값이 0이 되어서 0 + [1, 2] + [3, 4] 라는 결과가 나오게 되고,

TypeError: unsupported operand type(s) for +: 'int' and 'list'

라는 에러가 나오게 된다.
따라서 sum(a, [])를 하게 되면 [] + [1, 2] + [3, 4]가 되어서 [1, 2, 3, 4]라는 결과가 나오게 된다. 그러나 이중 리스트에서 가능한 것이므로 3차원 이상 중첩된 구조는 제대로 된 결과가 나오지 않을 수 있다.

이 문제는 이차원 리스트뿐만 아니라 3중 이상으로 Nested된 input도 있기 때문에 위에서 설명한 방법을 사용하면 안된다.

재귀함수를 이용하여 iterator가 현재 int를 가리키고 있으면 해당 정수를 결과값에 추가하고 int가 아닌 list일 경우 재귀함수로 들어가서 위의 과정을 반복한다. 즉,

1. 빈 배열 q = [] 선언

   def __init__(self, nestedList: [NestedInteger]):
       self.q = []
       self.flatten(nestedList)

2. 재귀함수 선언

   def flatten(self, nl):
       for i in nl:
   	      if i.isInteger():
               self.q.append(i.getInteger())
   
           else:
               self.flatten(i.getList())