(Python3) - LeetCode (Medium) : 2471. 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

O(n)으로 사이클을 통한 최소 swap 개수를 구하는 BFS 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

정답 변수 totalSwap과 bfs를 위한 deque dq를 선언 후 적절히 초기화해줍니다.

📔 풀이과정

1. 트리의 레벨별 bfs를 순회하도록 구현해줍니다. 현재 dq의 길이를 size로 두고 size만큼 dq의 원소를 popleft하며 순회하면 구할 수 있습니다. 이를 values배열에 append해줍니다. 

 

2. 레벨별 values를 인자로 받아 최소 사이클의 개수를 반환하는 함수 minCicle을 구현해줍니다. 해당 함수는 다음과 같이 동작합니다.

  2-1. values를 enumerate해 원소별 (value, index)로 만든 뒤 sorted함수로 value에 대한 오름차순으로 정렬해 sortedValueIdx배열에 저장합니다.

  2-2. values의 개수만큼 visited 배열을 선언 후 False로 초기화해줍니다.

  2-3. values의 원소를 순회하며 방문하지 않았고 이미 정렬된 경우 continue를, 아니라면 while loop를 수행하며 sortedValuesIdx내 index들을 순회하며 방문해주며 사이클의 길이를 구합니다.

  2-4. 사이클의 개수가 1을 초과한다면 swap이 필요하므로 사이클 길이 - 1을 반환합니다.

 

3. bfs로 각 레벨별 노드를 순회하며 사이클 개수를 totalSwap에 누적해 더해줍니다.

 

사이클이 왜 최소 스왑을 보장하는가?

• 배열을 정렬하는 문제는 본질적으로 값을 올바른 위치로 이동시키는 문제입니다.
• 정렬되지 않은 배열에서 값들의 이동 관계를 그래프로 나타내면 사이클 구조를 확인할 수 있습니다.
• 사이클의 핵심:
  • 하나의 사이클 내 값들은 서로 자리를 바꾸는 방식으로만 정렬이 가능합니다.
  • 사이클 내의 값 개수를 k라고 하면, k - 1번의 스왑으로 모든 값을 제자리로 이동시킬 수 있습니다.
  • 이외의 스왑은 불필요하며, 더 적은 스왑으로 사이클 내 값을 정렬하는 것은 불가능합니다.

예제:

배열 [8, 7, 6, 5]의 경우:

• 정렬된 형태: [5, 6, 7, 8].
• 원소 간의 이동 관계:
  • 8 → 5 → 6 → 7 → 8 (사이클 형성).
• 사이클 크기 = 4.
• 필요한 최소 스왑 = 4 - 1 = 3.

따라서, 사이클 기반 정렬은 불필요한 스왑을 방지하며 최소 스왑을 보장합니다.

---

시간 복잡도

• BFS 탐색: 모든 노드를 한 번 방문하므로 O(n).
• minCicle:
  • 각 레벨의 노드 수를 k라 할 때:
    • 정렬: O(k log k).
    • 사이클 탐색: O(k).
  • 따라서 minCicle의 시간 복잡도는 O(k log k).
• 트리의 모든 레벨에 대해 수행하면, 총 노드 수 n에 대해 O(n log n).

공간 복잡도

• BFS 큐와 레벨별 배열 저장에 필요한 공간: O(n).
• visited 및 sortedValuesIdx 배열의 크기: 각 레벨별 O(k).
• 최악의 경우, 트리의 레벨 중 가장 많은 노드 수(k ≈ n/2)가 필요하므로 최종적으로 O(n).

---

최종 풀이 요약

• 트리를 BFS로 레벨별 순회하여 각 레벨의 노드 값을 values 배열에 저장합니다.
• 각 레벨의 values 배열에서 사이클 기반 최소 스왑 횟수를 계산합니다.
• 모든 레벨의 스왑 횟수를 합산하여 트리의 정렬에 필요한 최소 스왑 횟수를 반환합니다.

 

 

📔 정답 출력 | 반환

totalSwap을 반환합니다.

---

📕 Code

📔 Python3

from collections import deque
# 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:
        def minCicle(values):
            n = len(values)
            visited = [False] * n
            sortedValIdx = sorted([(value, idx) for idx, value in enumerate(values)])
            swaps = 0
            for i in range(n):
                if visited[i] or sortedValIdx[i][1] == i:
                    continue
                cycleSize = 0
                x = i
                while not visited[x]:
                    visited[x] = True
                    x = sortedValIdx[x][1]
                    cycleSize += 1
                if cycleSize > 1:
                    swaps += (cycleSize - 1)
            return swaps            

        totalSwap = 0
        dq = deque([root])
        while dq:
            size = len(dq)
            values = []
            for i in range(size):
                front = dq.popleft()
                values.append(front.val)
                if front.left:
                    dq.append(front.left)
                if front.right:
                    dq.append(front.right)
            totalSwap += minCicle(values)

        return totalSwap

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.