[LeetCode] 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/description/

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

문제 유형: 정렬, 트리, bfs

문제 난이도: Medium

 

문제

You are given the root of a binary tree with unique values.

In one operation, you can choose any two nodes at the same level and swap their values.

Return the minimum number of operations needed to make the values at each level sorted in a strictly increasing order.

The level of a node is the number of edges along the path between it and the root node.

 

중복없는 값들을 가진 이진트리의 루트가 주어집니다.

한 번의 연산으로 같은 레벨의 두 노드를 골라 스왑할 수 있습니다.

레벨별로 오름차순 정렬되어있게 하기 위한 최소 연산횟수를 구하시오.

 

풀이

bfs를 하면서 같은레벨의 값들을 배열에 담아주면 된다.

한 레벨의 요소들의 배열에서 정렬횟수를 구하는건, 선택정렬 기반으로 알수 있는데,

기존 정렬된 게 있다면 빠르게 선택정렬 횟수를 구할 수 있다.

 

배열의 복사본 target을 만들어서 정렬시킨다.

기존 배열의(값, 인덱스)를 map에 저장한다.

 

기존배열 nums를 순차적으로 순회하면서:

  nums[i]와 target[i]을 비교하여 다르다면:

    연산횟수를 1 늘린다.

    이제, 이 위치에 걸맞는 수를 끌어와야한다. mp[target[i]]에는 nums[i]에서의 그 수의 인덱스 curPos가 저장되어있다.

    mp[nums[i]]에 curPos를 넣어서 map에는 nums[i]가 이제 curPos에 있다고 저장시킨다.

    nums[i]와 nums[curPos]를 스왑한다.

 

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int res = 0;
        vector<int> target = nums;
        sort(target.begin(), target.end());

        unordered_map<int, int> pos;
        for(int i = 0; i < nums.size(); ++i) {
            pos[nums[i]] = i;
        }

        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] != target[i]) {
                res++;

                int curPos = pos[target[i]];
                pos[nums[i]] = curPos;
                swap(nums[curPos], nums[i]);
            }
        }
        return res;
    }
    int minimumOperations(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int ans = 0;
        while(!q.empty()) {
            int qsize = q.size();
            vector<int> children;
            for(int i = 0; i < qsize; ++i) {
                auto curr = q.front();
                q.pop();

                if(curr -> left) {
                    children.push_back(curr -> left -> val);
                    q.push(curr -> left);
                }
                if(curr -> right) {
                    children.push_back(curr -> right -> val);
                    q.push(curr -> right);
                }
            }
            ans += minSwaps(children);
        }

        return ans;
    }
};