난이도 - Medium
Intuition
이 문제는 DFS와 BFS두가지로 풀 수 있다.
1) DFS
DFS는 Recursive한 함수를 사용해서 푸는 방법이다. 또한 함수에 파라미터로 depth를 tracking할 수 있는것을 집어 넣어야, 나중에 계산을 할때 사용할 수 있다.
class Solution:
def depthSum(self, nestedList: List[NestedInteger]) -> int:
return self.calcList(nestedList, 1)
def calcList(self, nestedList: List[NestedInteger], depth: int):
ans = 0
for item in nestedList:
if item.isInteger():
ans += item.getInteger() * depth
else:
ans += self.calcList(item.getList(), depth + 1)
return ansTime Complexity: O(n) 여기서 n은 nested elements의 총 개수이다. 예를 들어, [ [[[[1]]]], 2] 가 input으로 주어진다면, 4개의 nested lists가 있고 2개의 nested integers가 있으므로 총 n = 6이다.
Space Complexity: O(n) 정확히 말해서, space complexity는 O(d)이고 d는 maximum level of nesting in the input이다. 따라서 하나의 integer가 여러개의 nested list로 감싸져 있는 최악의 경우가 되어야 O(n)이 나온다.
2) BFS
BFS는 deque와 while문을 이용해서 풀 수 있다. while문 한번에 하나의 depth에 있는 모든 원소를 계산하고, 다음 depth를 계산하는 식으로 진행한다.
class Solution:
def depthSum(self, nestedList: List[NestedInteger]) -> int:
ans = 0
depth = 1
queue = deque()
queue.extend(nestedList)
while queue:
for i in range(len(queue)):
item = queue.popleft()
if item.isInteger():
ans += item.getInteger() * depth
else:
queue.extend(item.getList())
depth += 1
return ansTime Complexity: O(n)
Space Complexity: O(n) DFS에서는 nested list가 많을수록 space complexity가 늘어났지만, 반대로 BFS에서는 flat list가 길수록 space complexity가 늘어난다. 예를 들어, [1,2,3,4,5]같이 flat list는 BFS의 경우, space complexity가 worst case가 된다.