LeetCode - Height Checker

height checker

• Difficulty : easy

Students are asked to stand in non-decreasing order of heights for an annual photo.
Return the minimum number of students that must move in order for all students to be standing in non-decreasing order of height.
Notice that when a group of students is selected they can reorder in any possible way between themselves and the non selected students remain on their seats.

• 모든 학생이 줄지 않고 높이를 유지하기 위해 움직여야하는 최소 학생 수를 반환

example
Example 1:
Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation:
Current array : [1,1,4,2,1,3]
Target array : [1,1,1,2,3,4]
On index 2 (0-based) we have 4 vs 1 so we have to move this student.
On index 4 (0-based) we have 1 vs 3 so we have to move this student.
On index 5 (0-based) we have 3 vs 4 so we have to move this student.

Example 2:
Input: heights = [5,1,2,3,4]
Output: 5

Example 3:
Input: heights = [1,2,3,4,5]
Output: 0

• 다른 배열을 정렬하여 올바른 높이 순서를 만든 다음 두 배열을 비교하면 원하는 결과를 얻을 수 있다.

solution

• 작성 언어 : javascript
• Runtime : 64 ms

/**
 * @param {number[]} heights
 * @return {number}
 */
var heightChecker = function(heights) {
    
    let movedStudents = 0;
    const heightsOrigin = [...heights];
    heights.sort((a, b) => {
        if(a > b) {
            return 1;
        }
        
        if(a < b) {
            return -1;
        }
        
        return 0;
    });
   
    for(let i = 0; i < heights.length; i++) {
        if(heightsOrigin[i] != heights[i]) {
            movedStudents++;
        }
    }
   
    return movedStudents;    
};

• 시간복잡도 : O(n)
• 만약 정렬하면서 swap 된 수로 하는경우 테스트케이스에 걸린다.
• [1,1,4,2,1,3] 인 경우, 실제 swap 되는 과정은 2번만 하면 된다.(4 랑 1 교환, 4랑 3 교환) -> 이게 정답같지만 원본배열과 정렬된 배열에서 index 에서 매치되지 않은(변경된) 횟수를 반환해줘야 한다.