1051. Height Checker

https://leetcode.com/problems/height-checker

불러오는 중입니다...

 

정렬을 활용한 접근

정렬을 하고 정렬된 값과 비교하여 틀린 횟수를 출력

sort는 O(nlogn)의 시간 복잡도, 반복문은 O(n) 의 시간 복잡도? O(nLogn) + O(n)?

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        int sol = 0;
        vector<int> arr = heights;
        sort(arr.begin(), arr.end());

        for (int i = 0; i < heights.size(); i++) {
            if (heights[i] != arr[i]) {
                sol++;
            }
        }
        return sol;
    }
};

 

이방법외에는 빠르게 접근하는 방법이 생각나지 않는다.