[LeetCode] Height Checker

목차

• 문제
• 문제 풀이
  • 풀이 1 : 정렬후 비교
  • 풀이 2 : Counting Sort
• 알게 된 내용
• 출처

문제

• heights를 정렬했을 때의 위치와 기존 위치가 같지 않은 개수를 구하는 문제입니다.
• 예시

  • 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.

  • Input: heights = [5,1,2,3,4]
    Output: 5
    Explanation:
    heights:  [5,1,2,3,4]
    expected: [1,2,3,4,5]
    All indices do not match.

  • Input: heights = [1,2,3,4,5]
    Output: 0
    Explanation:
    heights:  [1,2,3,4,5]
    expected: [1,2,3,4,5]
    All indices match.

• 제약조건
  
  • 1 <= heights.length <= 100
  • 1 <= heights[i] <= 100

문제 풀이

풀이 1 : 정렬후 비교

• 풀이
  • 단순하게 정렬한 뒤에 해당 위치의 값이 같은지 비교하면 됩니다.
• 코드

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

     
• 시간복잡도
  • O(NlogN)

풀이 2 : Counting Sort

• 풀이
  • Counting Sort 방식은 값의 범위가 제한적이고, N의 크기가 클 때 사용할 수 있습니다. (값의 범위가 클 경우 Counting Sort 방식은 많은 메모리 낭비를 야기시킵니다.)
  • 문제에서는 heights[i]가 1부터 100까지로 값의 범위가 그렇게 크지 않기 때문에 Counting Sort 방식을 생각할 수 있습니다.
  • 이 방법을 적용하면 정렬알고리즘을 O(N+K)만에 해결이 가능합니다.
    • K는 값의 범위를 의미합니다.
    • 즉, NlogN 하고 비교해서 K가 logN에 보다 작을 경우 효율적인 알고리즘입니다.
• 코드

  • class Solution:
        def heightChecker(self, heights: List[int]) -> int:
            answer = 0
            
            count_list = [0 for _ in range(101)]
            for height in heights:
                count_list[height]+=1
            
            sorted_heights=[]
            for i in range(1,101):
                sorted_heights+=[i for _ in range(count_list[i])]
                
            for i in range(len(heights)):
                if sorted_heights[i]!=heights[i]:
                    answer+=1
            return answer

• 시간복잡도
  • O(N+K)

알게 된 내용

• 값의 범위가 제한적이고, n이 클 경우 counting sort 방식이 효율적입니다. (즉, 값의 범위를 K라고 한다면 K <logN일 경우 counting sort 방식이 효율적입니다.)

출처

• https://leetcode.com/explore/learn/card/fun-with-arrays/511/in-place-operations/3259/