[Leetcode] Diagonal Traverse

Problem)

 

Solution 1)

2중 for문을 사용해서 인덱스 i + j 값을 활용하여 리스트의 대각선 성분들끼리 묶을 수 있습니다. 예제의 경우 각 위치의 i + j 값은,

 

[[1, 2, 3],                [[0, 1, 2],

 [4, 5, 6],    ---->    [1, 2, 3],

 [7, 8, 9]]                [2, 3, 4]]

 

이와 같이 표현할 수 있기 때문에 O(n)의 복잡도로 모든 원소들을 대각선 묶음으로 저장해서 얻은 딕셔너리를 각 키 값의 성분들을 역순으로 출력하면 원하는 값을 얻을 수 있습니다.

 

d = {"0": [0], "1": [2, 4], "2": [3, 5, 7], "3": [6, 8], "4": [9]}

각 리스트들의 역순 reversed_d = {"0": [0], "1": [4, 2], "2": [7, 5, 3], "3": [8, 6], "4": [9]}

 

from collections import defaultdict

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        dic = defaultdict(list)
        I = len(nums)
        
        for i in range(I):
            for j in range(len(nums[i])):
                dic[i+j].append(nums[i][j])
                
        res = []
        
        for k in sorted(dic.keys()):
            res.extend(dic[k][::-1])
            
        return res

그런데 이러한 풀이법은 비슷한 유형의 문제를 접해보지 않은 사람이라면 그렇게 쉽게 생각해내기는 어려울 수도 있습니다. (제 경우에는 쉽게 이런 생각을 할 수 없었습니다...)

따라서 트리 구조를 적용한 다음과 같은 풀이법도 존재합니다.

 

Solution 2)

주어진 2차원 리스트을 트리 구조로 보고 BFS를 활용하면 원하는 결과를 얻을 수 있습니다.

 

주어진 리스트의 [0, 0]을 root node로 보고 [1, 0]을 left child, [0, 1]을 right child로 보면 우리는 주어진 리스트를 트리 구조로 변형 시켜서 생각할 수 있습니다.

 

이때 주의해야할 점은, 중복 child가 생길 수 있다는 것 입니다. 예를 들어 [1, 1]은 [1, 0]의 right child가 되는 동시에 [0, 1]의 left child가 될 수 있습니다. 따라서 우리는 이를 방지하기 위한 조건으로 가장 왼쪽에 있는 열 [:, 0]의 node들만 left child를 고려하게끔 만듭니다. 이렇게하면 node들 간의 중복된 child를 갖지 않게 됩니다.

 

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        ans = []
        m = len(nums)
        
        # [0, 0] root node를 가진 deque 생성
        queue = collections.deque([(0, 0)])
        
        while queue:
            row, col = queue.popleft()
            ans.append(nums[row][col])
            
            # 가장 좌측 열의 node(col == 0)만 left child를 고려
            if col == 0 and row + 1 < m:
                queue.append((row + 1, col))
                
            # right child
            if col + 1 < len(nums[row]):
                queue.append((row, col + 1))
            
        return ans