2471. Minimum Number of Operations to Sort a Binary Tree by Level

문제 링크


내 코드

55ms, 181.1MB

class Solution {
public:
    int minimumOperations(TreeNode* root) {
        int answer{};
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            vector<pair<int, int>> nodesWithIndex;
            int n{};
            for (int s{}, e{ static_cast<int>(q.size()) }; s < e; ++s) {
                auto now = q.front(); q.pop();
                if (now->left) {
                    q.push(now->left);
                    nodesWithIndex.emplace_back(now->left->val, n++);
                }
                if (now->right) {
                    q.push(now->right);
                    nodesWithIndex.emplace_back(now->right->val, n++);
                }
            }

            // 최소 교환횟수를 구하는 좋은 방법?
            sort(begin(nodesWithIndex), end(nodesWithIndex), [](const pair<int, int>& p1, const pair<int, int>& p2) {
                return p1.first < p2.first;
                });

            vector<bool> visited(n, false);
            int swapCnt{};

            for (int i{}; i < n; ++i) {
                // 이미 정렬된 위치이거나 방문한 노드인 경우 건너뜀
                if (visited[i] || nodesWithIndex[i].second == i) continue;

                int cycle_size = 0;
                int j = i;

                // 사이클을 탐색
                while (!visited[j]) {
                    visited[j] = true;
                    j = nodesWithIndex[j].second;
                    cycle_size++;
                }

                // 사이클의 크기가 0보다 클 경우 스왑 수 증가
                if (cycle_size > 0) {
                    swapCnt += (cycle_size - 1);
                }
            }

            answer += swapCnt;
        }
        return answer;
    }
};

최소 교환 횟수 구하기..

오름차순으로 정렬해야 하는 배열에서 최소 정렬 횟수를 구하는 방법은 문제의 정의에 따라 다를 수 있습니다. 여기서는 일반적으로 사용되는 몇 가지 접근 방식을 소개하겠습니다.

1. 인버전 수 (Inversion Count) 이용하기

인버전 수는 배열 내에서 앞에 위치한 원소가 뒤에 있는 원소보다 큰 쌍의 개수를 의미합니다. 인접한 두 원소를 교환하는 방식으로 정렬할 때, 전체 인버전 수이 최소 횟수가 됩니다.

  • 계산 방법:

    • 병합 정렬(Merge Sort)과 같은 효율적인 정렬 알고리즘을 활용하여 인버전 수를 계산할 수 있습니다. 시간 복잡도는 O(nlog⁡n)O(n \log n)입니다.

  • 적용 예:

    def merge_sort(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, inv_left = merge_sort(arr[:mid])
    right, inv_right = merge_sort(arr[mid:])
    merged, inv_split = merge(left, right)
    return merged, inv_left + inv_right + inv_split

def merge(left, right):
    result = []
    i = j = inv_count = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            inv_count += len(left) - i
            j += 1
    result += left[i:]
    result += right[j:]
    return result, inv_count

2. 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 이용하기

배열을 정렬하기 위해 최소한으로 이동해야 하는 원소의 수는 전체 원소 수에서 LIS의 길이를 뺀 값입니다.

  • 계산 방법:

    • 동적 프로그래밍(Dynamic Programming) 또는 이진 탐색(Binary Search)을 활용하여 LIS를 구할 수 있습니다. 시간 복잡도는 O(nlog⁡n)O(n \log n)입니다.

  • 적용 예:

    import bisect

def length_of_LIS(nums):
    sub = []
    for num in nums:
        idx = bisect.bisect_left(sub, num)
        if idx == len(sub):
            sub.append(num)
        else:
            sub[idx] = num
    return len(sub)

array = [10, 9, 2, 5, 3, 7, 101, 18]
lis_length = length_of_LIS(array)
min_moves = len(array) - lis_length

3. 사이클 기반 최소 스왑 수 (Minimum Swaps Using Cycle Detection)

배열을 정렬하기 위해 필요한 최소 스왑 수는 배열의 사이클 수를 이용해 계산할 수 있습니다.

  • 계산 방법:

    • 배열의 각 원소를 정렬된 위치와 비교하여 사이클을 형성하고, 각 사이클의 길이에서 1을 뺀 값을 모두 더합니다.

  • 적용 예:

    def min_swaps(arr):
    n = len(arr)
    arr_pos = sorted([(num, i) for i, num in enumerate(arr)], key=lambda it: it[0])
    visited = [False] * n
    swaps = 0

    for i in range(n):
        if visited[i] or arr_pos[i][1] == i:
            continue
        cycle_size = 0
        j = i
        while not visited[j]:
            visited[j] = True
            j = arr_pos[j][1]
            cycle_size += 1
        if cycle_size > 0:
            swaps += (cycle_size - 1)
    return swaps

array = [4, 3, 2, 1]
print(min_swaps(array))  # 출력: 2

요약

  • 인버전 수는 인접 교환을 기준으로 최소 정렬 횟수를 구할 때 유용합니다.
  • 최장 증가 부분 수열(LIS) 은 원소 이동을 기준으로 최소 정렬 횟수를 계산할 때 사용됩니다.
  • 사이클 기반 스왑 수는 임의의 두 원소를 교환할 수 있을 때 필요한 최소 스왑 수를 계산하는 데 적합합니다.

LIS를 이용하되 C++ 코드로 만들어주세요.

물론입니다! 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)을 이용하여 배열을 오름차순으로 정렬하기 위해 필요한 최소 이동 횟수를 계산하는 C++ 코드를 제공해드리겠습니다. 이 방법은 배열의 전체 원소 수에서 LIS의 길이를 빼면 최소 이동 횟수를 구할 수 있습니다.

아래는 C++로 작성된 예제 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>

// LIS의 길이를 O(n log n) 시간 복잡도로 계산하는 함수
int length_of_LIS(const std::vector<int>& nums) {
    std::vector<int> sub; // LIS를 구성하는 서브 시퀀스를 저장할 벡터

    for (const auto& num : nums) {
        // 현재 숫자가 서브 시퀀스의 마지막 숫자보다 크면 추가
        if (sub.empty() || num > sub.back()) {
            sub.push_back(num);
        }
        else {
            // 서브 시퀀스에서 현재 숫자보다 크거나 같은 첫 번째 숫자의 위치를 찾음
            auto it = std::lower_bound(sub.begin(), sub.end(), num);
            // 해당 위치의 숫자를 현재 숫자로 교체
            *it = num;
        }
    }

    return sub.size();
}

int main() {
    // 예제 배열
    std::vector<int> array = {10, 9, 2, 5, 3, 7, 101, 18};

    // LIS의 길이를 계산
    int lis_length = length_of_LIS(array);

    // 최소 이동 횟수 계산 (전체 원소 수 - LIS의 길이)
    int min_moves = array.size() - lis_length;

    // 결과 출력
    std::cout << "배열: ";
    for (const auto& num : array) {
        std::cout << num << " ";
    }
    std::cout << "\nLIS의 길이: " << lis_length;
    std::cout << "\n최소 이동 횟수: " << min_moves << std::endl;

    return 0;
}

코드 설명

  1. length_of_LIS 함수:

    • 이 함수는 주어진 배열 nums에서 최장 증가 부분 수열의 길이를 계산합니다.
    • sub 벡터는 현재까지 발견된 LIS를 구성하는 원소들을 저장합니다.
    • 배열을 순회하면서 현재 숫자가 sub의 마지막 원소보다 크면 sub에 추가합니다.
    • 그렇지 않으면 sub에서 현재 숫자보다 크거나 같은 첫 번째 원소를 찾아 현재 숫자로 교체합니다. 이를 통해 sub는 가능한 가장 작은 값들로 구성된 LIS의 길이를 유지하게 됩니다.
    • 최종적으로 sub.size()가 LIS의 길이가 됩니다.

  2. main 함수:

    • 예제 배열을 정의하고 length_of_LIS 함수를 호출하여 LIS의 길이를 계산합니다.
    • 최소 이동 횟수는 배열의 전체 원소 수에서 LIS의 길이를 뺀 값으로 계산됩니다.
    • 결과를 출력합니다.

실행 예시

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

배열: 10 9 2 5 3 7 101 18 
LIS의 길이: 4
최소 이동 횟수: 4

여기서 LIS는 [2, 3, 7, 101]으로, 길이는 4입니다. 따라서 최소 이동 횟수는 전체 원소 수인 8에서 4를 뺀 4가 됩니다.

추가 설명

  • 시간 복잡도: length_of_LIS 함수는 각 원소에 대해 이진 탐색을 수행하므로 전체 시간 복잡도는 O(n log n)입니다.
  • 공간 복잡도: 추가적인 벡터 sub를 사용하므로 공간 복잡도는 O(n)입니다.

근데 [7, 6, 5, 4]에서 LIS는 1인데 최소 교환 횟수는 2아닌가요? [7,4], [6,5] 교환하면 정렬되는데요?

맞습니다. 사용자가 제시한 [7, 6, 5, 4] 예제에서 **최장 증가 부분 수열 (LIS)**을 이용한 방법과 사이클 기반 최소 스왑 수를 이용한 방법이 서로 다른 결과를 도출하는 이유는 두 방법이 서로 다른 정렬 연산을 기준으로 하기 때문입니다.

정리하자면:

  • LIS를 이용한 방법 (최소 이동 횟수):
    배열을 정렬하기 위해 원소를 이동시키는 최소 횟수를 계산합니다. 이 경우, 최소 이동 횟수 = 배열의 크기 - LIS의 길이로 계산합니다.
    예제 [7, 6, 5, 4]에서는 LIS의 길이가 1이므로, 최소 이동 횟수는 4 - 1 = 3입니다. 이는 원소를 이동시켜 정렬할 때 필요한 최소 횟수입니다.

  • 사이클 기반 최소 스왑 수:
    배열을 정렬하기 위해 임의의 두 원소를 교환하는 최소 횟수를 계산합니다. 이 경우, 사이클의 수를 이용하여 계산합니다.
    같은 예제 [7, 6, 5, 4]에서는 2번의 스왑으로 정렬할 수 있습니다:

    • 첫 번째 스왑: 7과 4를 교환하여 [4, 6, 5, 7]
    • 두 번째 스왑: 6과 5를 교환하여 [4, 5, 6, 7]

따라서, 두 방법은 정렬을 수행하는 연산의 종류에 따라 다른 결과를 도출하게 됩니다. 사용자가 원래 의도한 최소 스왑 횟수를 구하고자 한다면, 사이클 기반 최소 스왑 수 방법을 사용해야 합니다.

사이클 기반 최소 스왑 수를 구하는 C++ 코드 제공

아래는 사이클 기반 최소 스왑 수를 구하는 C++ 코드입니다. 이 코드는 배열을 오름차순으로 정렬하기 위해 필요한 최소 스왑 횟수를 계산합니다.

#include <iostream>
#include <vector>
#include <algorithm>

// 최소 스왑 수를 계산하는 함수
int min_swaps(std::vector<int>& arr) {
    int n = arr.size();
    // 원소와 원래 인덱스를 저장하는 벡터
    std::vector<std::pair<int, int>> arr_pos(n);
    for (int i = 0; i < n; ++i) {
        arr_pos[i] = {arr[i], i};
    }

    // 원소를 기준으로 정렬
    std::sort(arr_pos.begin(), arr_pos.end(),
              [&](const std::pair<int, int>& a, const std::pair<int, int>& b) -> bool {
                  return a.first < b.first;
              });

    // 방문 여부를 표시하는 벡터
    std::vector<bool> visited(n, false);
    int swaps = 0;

    for (int i = 0; i < n; ++i) {
        // 이미 정렬된 위치이거나 방문한 노드인 경우 건너뜀
        if (visited[i] || arr_pos[i].second == i)
            continue;

        int cycle_size = 0;
        int j = i;

        // 사이클을 탐색
        while (!visited[j]) {
            visited[j] = true;
            j = arr_pos[j].second;
            cycle_size++;
        }

        // 사이클의 크기가 0보다 클 경우 스왑 수 증가
        if (cycle_size > 0) {
            swaps += (cycle_size - 1);
        }
    }

    return swaps;
}

int main() {
    // 예제 배열
    std::vector<int> array1 = {10, 9, 2, 5, 3, 7, 101, 18};
    std::vector<int> array2 = {7, 6, 5, 4};

    // 배열을 정렬하기 위한 최소 스왑 수 계산
    int swaps1 = min_swaps(array1);
    int swaps2 = min_swaps(array2);

    // 결과 출력
    std::cout << "배열1: ";
    for (const auto& num : array1) {
        std::cout << num << " ";
    }
    std::cout << "\n배열1을 정렬하기 위한 최소 스왑 수: " << swaps1 << std::endl;

    std::cout << "\n배열2: ";
    for (const auto& num : array2) {
        std::cout << num << " ";
    }
    std::cout << "\n배열2를 정렬하기 위한 최소 스왑 수: " << swaps2 << std::endl;

    return 0;
}

코드 설명

  1. min_swaps 함수:

    • 원소와 원래 인덱스를 저장:
      arr_pos 벡터에 배열의 원소와 그 원소의 원래 인덱스를 저장합니다.
    • 정렬:
      원소의 값을 기준으로 arr_pos를 정렬합니다. 이렇게 하면 각 원소가 최종적으로 위치해야 할 인덱스를 알 수 있습니다.
    • 사이클 탐색:
      각 원소가 자신의 정렬된 위치로 가기 위해 필요한 스왑을 계산하기 위해 사이클을 탐색합니다. 사이클의 크기가 k라면, k-1번의 스왑이 필요합니다.
    • 스왑 수 계산:
      모든 사이클에 대해 필요한 스왑 수를 합산하여 최소 스왑 수를 반환합니다.

  2. main 함수:

    • 두 가지 예제 배열을 정의하고, 각각에 대해 min_swaps 함수를 호출하여 최소 스왑 수를 계산합니다.
    • 결과를 출력합니다.

실행 예시

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다:

배열1: 10 9 2 5 3 7 101 18 
배열1을 정렬하기 위한 최소 스왑 수: 4

배열2: 7 6 5 4 
배열2를 정렬하기 위한 최소 스왑 수: 2

추가 설명

  • 시간 복잡도:

    • 정렬: O(nlog⁡n)O(n \log n)
    • 사이클 탐색: O(n)O(n) 따라서 전체 시간 복잡도는 O(nlog⁡n)O(n \log n)입니다.

  • 공간 복잡도:
    추가적으로 arr_pos와 visited 벡터를 사용하므로 O(n)O(n)의 공간 복잡도를 가집니다.

결론

  • LIS 기반 방법:

    • 용도: 원소를 이동시켜 배열을 정렬할 때 필요한 최소 이동 횟수 계산
    • 계산법: 최소 이동 횟수 = 배열의 크기 - LIS의 길이
    • 예시: [7, 6, 5, 4]에서 최소 이동 횟수는 3

  • 사이클 기반 최소 스왑 수:

    • 용도: 임의의 두 원소를 교환하여 배열을 정렬할 때 필요한 최소 스왑 횟수 계산
    • 계산법: 배열의 사이클을 탐색하여 각 사이클의 크기에서 1을 뺀 값을 합산
    • 예시: [7, 6, 5, 4]에서 최소 스왑 횟수는 2

Solution

Approach 1: Hash Map

  • 191ms, 212.67MB
  • Complexity
    • Let nn be the total number of nodes in the binary tree.
    • Time Complexity: O(nlog⁡n)O(n \log n)
    • Space Complexity: O(n)O(n)
class Solution {
public:
    int minimumOperations(TreeNode* root) {
        queue<TreeNode*> queue;
        queue.push(root);
        int totalSwaps = 0;

        // Process tree level by level using BFS
        while (!queue.empty()) {
            int levelSize = queue.size();
            vector<int> levelValues(levelSize);

            // Store values of current level and add children to queue
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                levelValues[i] = node->val;

                if (node->left != nullptr) queue.push(node->left);
                if (node->right != nullptr) queue.push(node->right);
            }

            // Add minimum swaps needed for current level
            totalSwaps += getMinSwaps(levelValues);
        }
        return totalSwaps;
    }

private:
    // Calculate minimum swaps needed to sort an array
    int getMinSwaps(vector<int>& original) {
        int swaps = 0;
        vector<int> target = original;
        sort(target.begin(), target.end());

        // Map to track current positions of values
        unordered_map<int, int> pos;
        for (int i = 0; i < original.size(); i++) {
            pos[original[i]] = i;
        }

        // For each position, swap until correct value is placed
        for (int i = 0; i < original.size(); i++) {
            if (original[i] != target[i]) {
                swaps++;

                // Update position of swapped values
                int curPos = pos[target[i]];
                pos[original[i]] = curPos;
                swap(original[curPos], original[i]);
            }
        }
        return swaps;
    }
};

GPT

아래 코드는 이진 트리의 각 레벨(층)마다 노드의 값들을 정렬하기 위해 필요한 최소 스왑(swap) 횟수를 합산한 결과를 구하는 알고리즘입니다. 즉, 트리의 레벨별로 주어진 노드 값들을 정렬할 때, 전체 스왑 횟수의 합을 계산합니다.

전체 로직

  1. BFS(너비 우선 탐색) 로 트리를 레벨 단위로 순회

    • 각 레벨의 노드들을 큐에서 꺼내어, 그 노드들의 값을 levelValues에 저장합니다.
    • 이때, 자식 노드(왼쪽·오른쪽)가 있으면 큐에 추가해서, 다음 레벨을 차례로 방문하게 합니다.

  2. 레벨 단위로 최소 스왑 계산

    • levelValues를 정렬하기 위해 필요한 최소 스왑 횟수를 구해 totalSwaps에 더해나갑니다.
    • 모든 레벨을 마치면, totalSwaps가 최종 결과가 됩니다.

코드 구조

int minimumOperations(TreeNode* root) {
    queue<TreeNode*> queue;
    queue.push(root);
    int totalSwaps = 0;

    // BFS로 트리 레벨 단위 접근
    while (!queue.empty()) {
        int levelSize = queue.size();
        vector<int> levelValues(levelSize);

        // 현재 레벨의 노드들을 꺼내며 값 저장
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = queue.front();
            queue.pop();
            levelValues[i] = node->val;

            if (node->left != nullptr) queue.push(node->left);
            if (node->right != nullptr) queue.push(node->right);
        }

        // 현재 레벨의 노드 값들을 정렬하는 데 필요한 스왑 횟수 계산
        totalSwaps += getMinSwaps(levelValues);
    }
    return totalSwaps;
}
  • queue에는 각 레벨의 노드들이 순차적으로 들어갑니다.
  • 한 레벨을 처리할 때마다 levelSize만큼 pop하여 해당 레벨의 모든 노드를 방문·처리한 뒤, 그 노드들의 자식(다음 레벨 노드들)은 push합니다.
  • 이렇게 BFS가 끝날 때까지 반복하면, 전체 트리를 레벨 단위로 처리한 것이 됩니다.

레벨별 최소 스왑 횟수: getMinSwaps

int getMinSwaps(vector<int>& original) {
    int swaps = 0;
    vector<int> target = original;
    sort(target.begin(), target.end());

    // 각 값이 현재 어떤 인덱스에 있는지 기록
    unordered_map<int, int> pos;
    for (int i = 0; i < original.size(); i++) {
        pos[original[i]] = i;
    }

    // 순서대로 target[i]가 오도록 swap
    for (int i = 0; i < original.size(); i++) {
        if (original[i] != target[i]) {
            swaps++;

            // target[i]값이 들어갈 위치(curPos)를 찾아 swap
            int curPos = pos[target[i]];
            pos[original[i]] = curPos;
            std::swap(original[curPos], original[i]);
        }
    }
    return swaps;
}
  1. 정렬된 상태(target) 와 현재 상태(original)를 비교
  2. 현재 배열 original 을 한 칸씩 확인(i 증가)하면서,
    • 만약 original[i]가 target[i]가 아니라면,
      1. target[i]가 있는 위치(curPos)를 찾는다. ( pos[target[i]] )
      2. original[i]와 original[curPos]를 swap하여, target[i]를 제자리에 둔다.
      3. swap 횟수 swaps++
      4. pos 맵을 갱신 (이전에 original[i]가 있던 곳에 target[i]가 들어갔으므로)
  3. 모든 원소가 target과 동일해질 때까지 진행 → 그 과정에서 발생한 swap 횟수가 정렬에 필요한 최소 횟수가 됩니다.

왜 최소 스왑?

  • 배열을 정렬할 때, 사이클 분해(cycle decomposition) 를 이용하면, 각 사이클에 필요한 스왑 횟수 = (사이클 길이 - 1)임이 알려져 있습니다.
  • 위 로직은 pos 맵을 사용해 직접 해당 사이클을 추적·교환하는 방법으로, 결과적으로 최소 swap 횟수를 구합니다.

핵심 요약

  1. 트리의 레벨 별로 노드 값을 추출 (levelValues).
  2. 각 레벨에서 getMinSwaps 함수를 이용해 그 레벨의 노드들을 정렬하는 데 필요한 스왑 횟수를 계산.
  3. 모든 레벨에 대해 구한 스왑 횟수를 합산한 값이 최종 결과.

즉, 한 층씩 내려가며 해당 층의 노드들을 단독으로 정렬한다고 가정했을 때, 각 층마다 필요한 스왑 횟수의 합을 구하는 문제인 것입니다.


Approach 2: Bit Manipulation

  • 257ms, 321.31MB
  • Complexity
    • Let nn be the total number of nodes in the binary tree.
    • Time Complexity: O(nlog⁡n)O(n \log n)
    • Space Complexity: O(n)O(n)
class Solution {
    // Constants for bit manipulation
    const int SHIFT = 20;
    const int MASK = 0xFFFFF;

public:
    int minimumOperations(TreeNode* root) {
        queue<TreeNode*> queue;
        queue.push(root);
        int swaps = 0;

        // Process tree level by level using BFS
        while (!queue.empty()) {
            int levelSize = queue.size();
            vector<long long> nodes(levelSize);

            // Store node values with encoded positions
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                // Encode value and index: high 20 bits = value, low 20 bits =
                // index
                nodes[i] = (static_cast<long long>(node->val) << SHIFT) + i;

                if (node->left != nullptr) queue.push(node->left);
                if (node->right != nullptr) queue.push(node->right);
            }

            // Sort nodes by their values (high 20 bits)
            sort(nodes.begin(), nodes.end());

            // Count swaps needed to match indices with original positions
            for (int i = 0; i < levelSize; i++) {
                int origPos = static_cast<int>(nodes[i] & MASK);
                if (origPos != i) {
                    // Swap nodes and decrement i to recheck current position
                    swap(nodes[i], nodes[origPos]);
                    swaps++;
                    i--;
                }
            }
        }
        return swaps;
    }
};

GPT

이 코드는 이진 트리(TreeNode* root)에서 각 레벨(층)에 존재하는 노드들의 값을 오름차순으로 정렬 하기 위해 필요한 스왑(swap) 횟수를 모두 합산하는 로직입니다.
기존 구현과 달리, 노드의 값과 해당 레벨 내에서의 인덱스를 하나의 64비트 정수(long long)에 비트로 인코딩하여 저장하고, 정렬 후 다시 인덱스를 맞춰 주는 방식으로 스왑 횟수를 계산하고 있습니다.

주요 아이디어

  1. 레벨별(BFS) 접근

    • BFS(너비 우선 탐색)로 트리를 한 레벨씩 처리합니다.
    • queue를 사용하여, 현재 레벨의 모든 노드를 꺼낸 후, 그 자식 노드를 다음 레벨 큐에 넣는 방식으로 진행합니다.

  2. 노드의 (값, 인덱스)를 하나의 수로 인코딩

    • 각 레벨에서 levelSize만큼 노드를 뽑아, 이 노드들이 “해당 레벨”에서 인덱스 0부터 levelSize−1\text{levelSize}-1까지 순서대로 들어왔다고 칩시다.
    • nodes[i]에 다음을 저장: (node->val << SHIFT)+i\text{(node->val << SHIFT)} + i
      • 여기서 SHIFT는 20, MASK가 0xFFFFF(20비트)
      • 즉, 상위 20비트는 노드의 값(node->val), 하위 20비트는 “레벨 내 인덱스(i)”입니다.
      • 이렇게 하면 한 변수 안에 (값, 인덱스)를 함께 담을 수 있습니다.

  3. 정렬: 노드 값 기준 (상위 20비트) 오름차순

    • sort(nodes.begin(), nodes.end())를 하면, C++ STL 정렬은 기본적으로 원소의 숫자 크기를 기준으로 정렬합니다.
    • 이때, node->val << SHIFT가 숫자 크기에 결정적 영향을 주므로, 값이 작은 순으로 오름차순이 됩니다.
    • 정렬 후, nodes[i]가 “원래는 i번째 위치(인덱스)에 있어야 할 노드”라는 의미입니다(값 기준으로 정렬된 상태).

  4. 스왑 계산: 최소 스왑으로 인덱스를 맞추기

    • 정렬을 마친 뒤, nodes[i]가 실제로 레벨 내 인덱스 i에 있어야 합니다.
    • 하지만, nodes[i]의 하위 20비트(origPos)를 보면, 이 노드가 원래 몇 번째 인덱스에서 왔는지 알 수 있습니다.
    • 만약 origPos != i라면, “현재 i 위치에는 origPos에서 온 노드가 잘못 자리해 있다”는 뜻이므로, 스왑을 통해 맞춰 줍니다.
      • 스왑 후, 다시 i 위치를 재확인하기 위해 i--로 한 칸 뒤로 되돌려(루프에서 i++가 곧 진행되므로, 결국 같은 위치를 다시 체크), 교정된 위치가 올바른지 또 확인하는 방식입니다.
      • 이 로직은 사이클(cycle)을 풀어 정렬할 때 자주 쓰는 기법으로, 결과적으로 최소 스왑 횟수를 계산하게 됩니다.

코드 흐름 요약

int minimumOperations(TreeNode* root) {
    const int SHIFT = 20;     // 상위 20비트로 값 저장
    const int MASK  = 0xFFFFF;  // 하위 20비트(=원래 인덱스) 추출용
    queue<TreeNode*> queue;
    queue.push(root);

    int swaps = 0;

    while (!queue.empty()) {
        int levelSize = queue.size();
        vector<long long> nodes(levelSize);

        // (A) 현재 레벨 노드들을 꺼내서, (값<<SHIFT + i)로 저장
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = queue.front();
            queue.pop();

            long long encoded = (static_cast<long long>(node->val) << SHIFT) + i;
            nodes[i] = encoded;

            // 다음 레벨 노드 준비
            if (node->left)  queue.push(node->left);
            if (node->right) queue.push(node->right);
        }

        // (B) 값(상위 20비트) 기준 오름차순 정렬
        //     즉, node->val이 작은 순서
        sort(nodes.begin(), nodes.end());

        // (C) 정렬된 상태에서, 인덱스 i에 있어야 할 원소가
        //     실제로 i의 위치가 맞는지 확인 & 스왑
        for (int i = 0; i < levelSize; i++) {
            int origPos = static_cast<int>(nodes[i] & MASK);

            if (origPos != i) {
                // 인덱스 origPos와 swap
                swap(nodes[i], nodes[origPos]);
                swaps++;
                i--;  // 이 위치를 다시 검사
            }
        }
    }
    return swaps;
}

복잡도 & 특이사항

  • 시간 복잡도

    • 트리의 총 노드가 NN개라고 할 때, BFS로 레벨마다 노드를 모아서 정렬합니다.
    • 최악의 경우(한 레벨이 매우 많거나, 예를 들어 완전 이진 트리에서 말단 레벨이 N/2 정도 차지) ⇒ 정렬에 O(Klog⁡K)O(K \log K)가 걸릴 텐데, 각 레벨 합이 결국 전체 NN.
    • 결과적으로 전체 트리를 한 번 순회 + 정렬이 합쳐져 O(Nlog⁡M)O(N \log M) 정도가 되며, 여기서 MM은 최대 레벨 크기( 보통 M≤NM \le N ), 실제로는 대략 O(Nlog⁡N)O(N \log N) 안에 해결 가능합니다.

  • 비트 인코딩은 “하나의 64비트에 (값, 인덱스)를 담아 정렬 시 편의”를 위해 쓴 트릭입니다.

    • 주의: 노드의 값(node->val)이 20비트를 초과하는 경우(즉, ∣val∣≥220|val| \ge 2^{20} 이상)라면, 상위 20비트에 인덱스를 넣을 수 없어 충돌이 일어날 수 있습니다.
    • 문제에서 허용되는 값 범위에 따라 이 트릭을 쓸 수 있습니다. 만약 값이 매우 클 수 있다면, 별도로 pair<int, int> 구조체 정렬을 사용하는 편이 안전합니다.

결론

  • 이진 트리를 레벨별로 나누어, 각 레벨을 값의 오름차순으로 “정렬해야 할 때” 필요한 스왑 횟수를 구하는 문제입니다.
  • 레벨마다 노드의 값·인덱스를 기록하고, 값 기준으로 정렬한 뒤, 인덱스를 맞추는 데 필요한 스왑 횟수를 누적합니다.
  • 비트 연산(SHIFT, MASK)을 사용해 한 long long 변수에 (값, 인덱스)를 인코딩하여 정렬과 원래 인덱스 추적을 동시에 처리하고 있습니다.