Counting Sort 1

문제

코드

def countingSort(arr):
    # 이전 코드
    # countArr = list(0 for i in range(len(arr)))
    #####################################################
    
    # 변경 코드
    # arr배열 크기의 조건은 10의 6제곱 까지이나
    # '0 <= arr[i] < 100'의 조건을 만족시키기 위해 다음 코드로 변경 
    countArr = list(0 for i in range(100))

    # counting sort
    for num in arr:
        countArr[num] += 1

    return countArr

새로 알게된 지식

인덱스 크기
arr리스트의 범위는 100 <= n <= 10^6 이지만
countArr의 인덱스 범위가 될 arr[i]의 범위는 0 <= arr[i] < 100 이다.
따라서 처음의 코드대로 countArr = list(0 for i in range(len(arr))) 실행하면
countArr의 범위가 100이상으로 넘어가는 예외가 생기므로
countArr = list(0 for i in range(100)) 코드로 수정하여 countArr의 범위를 100으로 지정하도록 변경했다.

출처

https://www.hackerrank.com/challenges/one-month-preparation-kit-countingsort1/problem?h_l=interview&isFullScreen=false&playlist_slugs%5B%5D=preparation-kits&playlist_slugs%5B%5D=one-month-preparation-kit&playlist_slugs%5B%5D=one-month-week-one