leetcode medium : Minimum Number of Operations to Sort a Binary Tree by Level

https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/

 

아니 .. cycle sort  너무 어렵다...

level by level traversal을 하면서 level별로 리스트를 구성하고

리스트의 각 요소들이 정렬됐을때 어디있어야 하는지 보고 swap하는게 핵심이다.

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        level_nodes = deque([root])
        answer = 0
        
        while level_nodes:
            level_count = len(level_nodes)
            
            # 정렬하고 최소 swap 세기
            imap = {} # value -> index 맵
            original = [] # 원래 순서대로 담겨있는 리스트
            _sorted = [] # 정렬된 리스트
            for i in range(level_count): # 리스트랑 맵 채우기
                imap[level_nodes[i].val] = i
                original.append(level_nodes[i].val)
                _sorted.append(level_nodes[i].val)
            _sorted.sort() # 정렬하기
            for i in range(level_count):
                if original[i] != _sorted[i]: # i번째 요소가 제자리에 있는게 아니면
                    """
                    1. 원본 리스트에서 (정렬된 리스트의 i번째 요소가 원래 있었던 위치)에 
                       원본 리스트의 i번째 요소를 넣어준다.
                    2. 맵에서 (원본리스트의 i번째 요소)가 가리키는 인덱스를 바뀐 위치로 수정해준다.
                    3. 맵에서 (정렬된 리스트의 i번째 요소)가 가리키는 인덱스를 수정해준다.
                    4. 원본리스트의 i번째 요소를 정렬된 리스트의 i번째 요소로 바꿔준다.
                    """
                    
                    """ example
                    원본리스트 = [2, 3, 4, 1]
                    정렬된리스트 = [1, 2, 3, 4]
                    
                    1. i = 0
                    정렬된리스트[i] = 1
                    1이 원래 있었던 인덱스 = 3
                    
                    원본리스트에서 i번째요소(2)랑 정렬된리스트[i] (=1)을 바꾼다.
                    [1, 3, 4, 2]
                    
                    2. i = 1
                    정렬된리스트[i] = 2
                    2의 원본리스트 인덱스 = 3
                    
                    원본리스트의 i번째요소(3)와 정렬된리스트[i] =(2)를 바꾼다.
                    [1, 2, 4, 3]
                    
                    ...
                    
                    핵심은 원본리스트의 i번째 요소에 맞는 값을 가져오는 것
                    """
                    original[imap[_sorted[i]]] = original[i]
                    imap[original[i]] = imap[_sorted[i]]
                    imap[_sorted[i]] = i;
                    original[i] = _sorted[i]
                    answer += 1
            
            # 다음 레벨 노드들 추가
            for i in range(level_count):
                node = level_nodes[i]
                
                if node.left:
                    level_nodes.append(node.left)
                if node.right:
                    level_nodes.append(node.right)
            
            # 이전 레벨 노드들 빼기
            for i in range(level_count):
                level_nodes.popleft()
                
        return answer