[leetcode] Height Checker

Height Checker

처음에 생각한 접근법

입력받은 리스트를 정렬해서 기존의 리스트와 비교한다.
[1,1,4,2,3] -> [1,1,2,3,4] 3개가 다르네!

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        sortedHeights = sorted(heights)
        result = 0
        
        for index in range(len(heights)):
            if heights[index] != sortedHeights[index]:
                result += 1
                
        return result

이렇게 해도 통과는 되는데 sorted를 사용하지 않고 푸는 방법이 궁금했다.

다른 사람 풀이

counting sort를 한다. heights에 있는 숫자의 개수를 freq에 적어둔 뒤에 heights의 순서와 다르면 result += 1을 한다.

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        result = 0
        curHeight = 0
        freq = [0]*101
        
        for height in heights:
            freq[height] += 1
        
        for i in range(len(heights)):
            while freq[curHeight] == 0: curHeight += 1
            
            if curHeight != heights[i]:
                result += 1
            
            freq[curHeight] -= 1
        
        return result

freq는 heights의 길이에 상관없이 일정한 크기를 갖고 있고 while문에서 freq 크기만큼 돌기 때문에 while문은 O(1)이다. 따라서 for-while은 heights의 길이와 비례하게 O(N)이 되어 전체적으로 O(N)이다.

참고 자료

John Leonardo