12. Height Checker

문제

https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/3228/

height는 학생들의 키가 랜덤으로 저장된 배열이다.

expected는 학생들 키를 순서대로 정렬한 배열이다.

heights[i]가 expected[i]가 아닌 인덱스의 개수를 반환하라.

Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation: 
heights:  [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.

 

내가 해결한 방법(c++)

새 배열 arr에 heights를 복사하고

c++의 algorithm 라이브러리에 있는 sort()를 사용하여 arr 정렬.

정렬 후 arr, heights 요소를 하나씩 비교하며 다른 요소 있을 때 count값 증가.

space complexity : O(n)

time complexity : sort 함수 성능이 O(n log n)이기 때문에 O(n log n)

int heightChecker(vector<int>& heights){
    // 새 배열 arr에 heights 복사
    vector<int> arr = heights

    // arr 정렬
    sort(arr.begin(), arr.end());

    // arr와 heights 비교하며 다른 요소 있을 때 count값 증가
    int count = 0;
    for (int i = 0; i < arr.size(); i++){
        if (arr[i] != heights[i]){
            count++;
        }
    }

    return count;
}

 

다른 해결 방식(python)

def heightChecker(self, heights: List[int]) -> int:
    return sum(x != y for x, y in zip(heights, sorted(heights)))

zip(iterable, iterable)이란?

두 개의 iterable을 인자로 받아 두 iterable의 각 인자를 순서대로 튜플로 묶어주는 함수.

numbers = [1, 2, 3]
characters = ['a', 'b', 'c']
for item in zip(numbers, characters):
   print(item)
    # (1, 'a')
    # (2, 'b')
    # (3, 'c')