머쓱이보다 키 큰 사람 - Python

def solution(array, height):
    return sum([1 for item in array if item > height])


# Test Cases
print(solution([149, 180, 192, 170], 167))
print(solution([180, 120, 140], 190))

  이 코드의 시간복잡도는 O(N)입니다.

 

---

def solution(array, height):
    array.append(height)
    array.sort(reverse=True)
    return array.index(height)

  꽤나 재미있는 코드를 발견했습니다. 시간복잡도는 아래의 계산 과정을 거칩니다. sort()의 메서드는 시간복잡도를 얼마나 차지하는지 궁금하기도 했었는데 좋은 공부가 되네요.

---

array.append(height)

  array 리스트에 height 값을 추가하면 리스트의 크기는 n+1이 됩니다.

 

array.sort(reverse=True)

  리스트의 크기가 n+1일 때 Timsort 알고리즘을 사용하여 내림차순으로 정렬됩니다. 정렬의 시간 복잡도는 O((n+1) log (n+1))입니다.

 

return array.index(height)

  정렬된 리스트에서 height의 인덱스를 찾는데 드는 시간은 O(n)입니다. (정확한 인덱스를 찾기 위해 최대 n번의 비교가 필요합니다)

  따라서 전체 시간 복잡도는 O((n+1) log (n+1)) + O(n)입니다. 리스트의 크기가 커질수록 정렬 단계가 주요 시간을 소비하므로 전체 시간 복잡도는 대부분 O(n log n)에 가깝게 될 것입니다. 이러한 이유로 시간 복잡도는 O(n log n)입니다.

 

---

• 프로그래머스: https://school.programmers.co.kr/learn/courses/30/lessons/120585

프로그래머스