341. Flatten Nested List Iterator

Flatten Nested List Iterator - LeetCode

 

# """
# 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]):
        
    
    def next(self) -> int:
        
    
    def hasNext(self) -> bool:
         

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

문제를 정리하면 다음과 같다.

NestedInteger 객체로 구성된 list가 입력값으로 들어온다. NestedInteger는 3가지 메서드(isInteger(), getInteger(), getList())를 지원한다. 주어진 NestedInteger를 파싱 해서 1차원 list로 반환하는 것이 문제의 요구사항이다.

 

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

위 입력값은 아래 3개의 NestedList 객체로 구성된 길이 3의 list이다. 출력하면 다음과 같다.

NestedInteger{_integer: None, _list: [NestedInteger{_integer: 1, _list: []}, NestedInteger{_integer: 1, _list: []}]}
NestedInteger{_integer: 2, _list: []}
NestedInteger{_integer: None, _list: [NestedInteger{_integer: 1, _list: []}, NestedInteger{_integer: 1, _list: []}]}

NestedInteger의 _integer가 True라면 정수라는 뜻이고, False라는 뜻은 NestedList로 구성된 List라는 뜻이다.

비교해보면서 읽으면 이해가 갈 것이다.

 

아무튼 이런 식으로 다차원의 정수 배열이 입력값으로 들어오면 평탄화해서 1차원 배열로 바꾸는 것이 문제의 요구사항이다.

위의 예제 같은 경우 [1, 1, 2, 1, 1]을 반환해야 정답이다.

 

실제로 NestedInteger 클래스를 건드릴 필요는 없고 주어진 3개의 메서드를 활용해서 NestedIterator 클래스를 완성하면 된다. hasNext(), next() 함수에 대한 정의 또한 문제에 있지만 이 또한 요구사항대로 구현하지 않아도 된다. 물론 추가 메서드를 구현해도 된다.

아무튼 결과적으로 아래의 pseudo code를 실행해서 결과가 나오게만 하면 된다... 는 것이 문제 설명이다.

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

이번 문제는 제대로 내가 풀지 못했기 때문에 괜찮다고 생각한 풀이를 다양하게 discussion page에서 찾아서 이해 후 작성했다.

 

1. DFS

from collections import deque


class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.deque = deque([])
        self.dfs(nestedList)

    def dfs(self, input_list):
        for item in input_list:
            if item.isInteger():
                self.deque.append(item.getInteger())
            else:
                self.dfs(item.getList())

    def next(self) -> int:
        return self.deque.popleft()

    def hasNext(self) -> bool:
        return self.deque

중첩된 배열은 DFS를 이용해서 탐색할 수 있다. 중첩된 배열을 DFS로 탐색해서 미리 결과를 만들어놓은 뒤 deque를 이용해 앞에서부터 하나씩 꺼내는 방법이다.

 

2. Stack

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = nestedList[::-1]

    def next(self) -> int:
        return self.stack.pop().getInteger()

    def hasNext(self) -> bool:
        while self.stack:
            if self.stack[-1].isInteger():
                return True
            else:
                temp = self.stack.pop()
                self.stack += temp.getList()[::-1]
        return False

스택을 사용한 풀이다. 포인트는 입력된 배열을 뒤집어서 가지고 시작한다는 점인데, 스택은 tail 부분만 꺼낼 수 있기 때문에 위와 같은 방법으로 시작한다. 스택의 tail이 정수면 그대로 꺼내서 반환하면 되고, 정수가 아니라면 list라는 뜻이기 때문에 꺼낸 뒤 getList() 함수를 뒤집어서 기존 stack에 extend 해준다. 포인트는 꺼낸 list도 뒤집어서 넣어줘야 한다는 점.

 

3. Deque

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

    def help(self):
        while self.q and not self.q[0].isInteger():
            temp = self.q.popleft()
            for item in temp.getList()[::-1]:
                self.q.appendleft(item)

    def next(self) -> int:
        if self.q[0].isInteger():
            return self.q.popleft().getInteger()
        else:
            self.help()
            return self.next()

    def hasNext(self) -> bool:
        self.help()
        return self.q

deque를 사용한 풀이다. 1번이랑 다른 점은 1번은 단순히 앞에서 꺼낼 때 효율적으로 꺼내기 위해서 사용한 것인데, 이 풀이 같은 경우는 좀 다르다. 근본적으로 보면 stack풀이와 매우 유사하지만 deque는 앞, 뒤에서 전부 꺼낼 수 있기 때문에 선언할 때 뒤집어서 선언하지 않아도 된다. 그래서 앞에서부터 값을 꺼내서 볼 수 있고 꺼낸 값이 정수면 그대로 반환하고, 그렇지 않다면 꺼낸 값에 getList()를 통해 얻은 list를 뒤집어서 appendleft() 연산을 통해 넣어주면 순서 그대로 유지하면서 연산을 할 수 있다.

 

4. Iterator 구현

class NestedIterator(object):

    def __init__(self, nestedList):
        self.stack = [[nestedList, 0]]

    def next(self):
        # self.hasNext()
        nestedList, i = self.stack[-1]
        self.stack[-1][1] += 1
        return nestedList[i].getInteger()
            
    def hasNext(self):
        s = self.stack
        while s:
            nestedList, i = s[-1]
            if i == len(nestedList):
                s.pop()
            else:
                x = nestedList[i]
                if x.isInteger():
                    return True
                s[-1][1] += 1
                s.append([x.getList(), 0])
        return False

사실 이 문제는 iterator를 구현하는 문제다. 그러니깐 엄밀히 따지고 보면 1, 2, 3번 풀이는 iterator를 구현한 것이 아니니깐 요구 사항과 다른 풀이다. 이 코드는 직접 iterator의 원리를 그대로 구현한 코드다.

설명하기 굉장히 어렵지만 예제 입력값을 가지고 한 번만 연습장에 시뮬레이션해보면 박수를 칠 정도의 풀이라고 생각한다.

 

5. generator, yield 구현(Python 한정)

def find_integer(input_list):
    if input_list.isInteger():
        yield input_list.getInteger()
    else:
        for item in input_list.getList():
            yield from find_integer(item)


def to_iteration(input_list):
    for item in input_list:
        yield from find_integer(item)


class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.generator = to_iteration(nestedList)
        self.val = None

    def next(self) -> int:
        return self.val

    def hasNext(self) -> bool:
        try:
            self.val = next(self.generator)
            print(self.val)
            return True
        except:
            return False

python의 고급(?) 문법 중 하나인 generator와 yield를 사용한 풀이다.

사실 python에서 직접 iterator를 구현하는 것은 yield를 사용하라는 것과 같기 때문에 위와 같은 풀이로 iterator를 호출할 때마다 조건에 맞는 값을 반환할 수 있다.

 

 

사실 1, 2, 3번 방법의 경우 결은 유사하다.

문제 요구 사항이 iterator를 구현하라는 것이었기 때문에 yield를 쓰는 것은 python에서만 지원하는 거니깐 사용하고 싶지 않았고(잘 사용할 줄도 모르고...), 그러다 보니 어떻게 iterator를 구현할 수 있는지에 대해 고민하다가 결국 GG 친 문제다.