문제 링크

https://www.hackerrank.com/challenges/insertion-sort/problem

주의사항

• 주어진 배열의 길이가 최대 10의 5승까지 가능하므로 시간 초과에 유의하며 풀어야 한다.

문제 풀이

• 시간 초과

def insertionSort(arr):
    tmp_arr = [0]
    tmp_arr.extend(arr)
    cnt = 0
    for i in range(2, len(tmp_arr)):
        for j in range(0, i):
            if tmp_arr[i] < tmp_arr[j]:
                tmp_arr = tmp_arr[:j]+[tmp_arr[i]]+tmp_arr[j:i]+tmp_arr[i+1:]
                cnt += (i-j)
    return cnt

• array 및 bisect 사용

from bisect import bisect_right
from array import array

def insertionSort(arr):
    tmp_arr = array('i', [arr[0]]) # array 초기화
    cnt = 0
    
    for i in range(1, len(arr)):
        idx = bisect_right(tmp_arr, arr[i]) # arr[i]의 위치찾기
        tmp_arr.insert(idx, arr[i]) # array에 arr[i] 넣기 # insert(위치, 값)
        cnt += abs(i-idx)
    return cnt

• 바로 저번 문제에서 bisect를 써놓고도 bisect를 활용하지 못해서 아쉽다...
• array를 하나 더 만들 생각을 못했다...