LeetCode - 2340. Minimum Adjacent Swaps to Make a Valid Array

처음 풀이.

주어진 vector를 정렬해서 min값, max값을 찾고,

find를 사용해서 앞에서부터 첫 min값까지의 거리(index), 뒤에서부터 첫 max값까지의 거리를 찾고,

min이 max보다 뒤에 있으면 둘 더한 값에 -1(테스트케이스 1의 경우처럼 min값이 한 칸 앞으로 올 수 있음),

min이 max보다 앞에 있으면 그냥 둘 더한 값을 반환.

class Solution {
public:
    int minimumSwaps(vector<int>& nums) {
        vector<int> tmp_num = nums;
        sort(tmp_num.begin(), tmp_num.end());
        int min_num = tmp_num[0];
        int max_num = tmp_num[tmp_num.size() - 1];
        int min_idx = distance(nums.begin(), find(nums.begin(), nums.end(), min_num));
        int max_idx = distance(nums.rbegin(), find(nums.rbegin(), nums.rend(), max_num));
        // cout << "min_idx: " << min_idx << ", min: " << min_num;
        // cout << " max_idx: " << max_idx << ", max: " << max_num << endl;
        if ((max_idx + min_idx) >= nums.size())
            return max_idx + min_idx - 1;
        return max_idx + min_idx;
    }
};

조금 오래 걸렸다.

sort 1번, find 2번으로 O(nlogn + 2n)

 

그래서 다른 사람 풀이를 보니까 모든 수를 순회하면서 min값, max값, min index값, max index값을 한 번에 찾음.

O(n)이 걸려서 더 좋은 것 같다.

class Solution {
public:
    int minimumSwaps(vector<int>& nums) {
        int min_num, max_num, min_idx, max_idx;
        min_num = nums[0];
        max_num = nums[0];
        min_idx = 0;
        max_idx = 0;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            if (nums[i] < min_num) {
                min_num = nums[i];
                min_idx = i;
            }
            if (nums[i] >= max_num) {
                max_num = nums[i];
                max_idx = i;
            }
        }
        if (max_idx < min_idx)
            return n - max_idx - 1 + min_idx - 1;
        return n - max_idx - 1 + min_idx;
    }
};

훨씬 빨리 걸렸다.