[HackerRank] Insertion Sort Advanced Analysis

⭐ 나의 풀이

#!/bin/python3

import math
import os
import random
import re
import sys
import bisect
from array import array
#
# Complete the 'insertionSort' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER_ARRAY arr as parameter.
#

def insertionSort(arr):
    # Write your code here
    result = 0
    result_arr = array('i', [arr[0]])
    for i in range(1, len(arr)) :
        idx = bisect.bisect_right(result_arr, arr[i])
        result_arr.insert(idx, arr[i])
        result += abs(i - idx)
    return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        n = int(input().strip())

        arr = list(map(int, input().rstrip().split()))

        result = insertionSort(arr)

        fptr.write(str(result) + '\n')

    fptr.close()

삽입 정렬을 하는 과정에서 원소가 총 얼만큼 움직였는지를 구해야 한다.

아래랑 똑같은 로직인데 자료구조만 리스트 ➡️ 배열로 변경했을 뿐인데 시간초과가 나지 않는다.

같은 데이터 타입을 담을거면 배열을 쓰는 게 효율적으로 메모리를 사용할 수 있다.

[2, 1, 3, 1, 2] 정렬 과정

 

# 시간초과
#!/bin/python3

import math
import os
import random
import re
import sys
import bisect

#
# Complete the 'insertionSort' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER_ARRAY arr as parameter.
#

def insertionSort(arr):
    # Write your code here
    result = 0
    result_arr = [arr[0]]
    for i in range(1, len(arr)) :
        idx = bisect.bisect_right(result_arr, arr[i])
        result_arr.insert(idx, arr[i])
        result += abs(i - idx)
    return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        n = int(input().strip())

        arr = list(map(int, input().rstrip().split()))

        result = insertionSort(arr)

        fptr.write(str(result) + '\n')

    fptr.close()

흠... 리스트의 insert 메서드로 바꿔봐도 시간 초과는 여전하다.

 

 

# 시간 초과
#!/bin/python3

import math
import os
import random
import re
import sys
import bisect

#
# Complete the 'insertionSort' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER_ARRAY arr as parameter.
#

def insertionSort(arr):
    # Write your code here
    result = 0
    result_arr = [arr[0]]
    for i in range(1, len(arr)) :
        idx = bisect.bisect_right(result_arr, arr[i])
        bisect.insort_right(result_arr, arr[i])
        result += abs(i - idx)
    return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        n = int(input().strip())

        arr = list(map(int, input().rstrip().split()))

        result = insertionSort(arr)

        fptr.write(str(result) + '\n')

    fptr.close()

아무래도 시간 초과의 원인은 bisect.insort_right 메소드다.

내부적으로 bisect_right()를 한번 더 사용하기 때문이다.😅

 

 

🟨 다른 사람 풀이

# https://programs.programmingoneonone.com/2021/07/hackerrank-insertion-sort-advanced-analysis-problem-solution.html
from array import array
from bisect import bisect_right

t = int(input())
for _ in range(t) :
    n = int(input())
    arr = array('I', [int(i) for i in input().split()])
    sarr = array('I', [arr[0]])
    result = 0
    for i in range(1, n) :
        e = arr[i]
        j = bisect_right(sarr, e)
        sarr.insert(j, e)
        result += i - j
    print(result)

이 코드를 보면 array를 선택한 이유가 있다.

리스트로 바꿔서 실행하면 시간초과가 뜬다.

자연수만 저장할거니까 리스트보다 array를 사용하는 것이 메모리 측면에서도 효율적이다.

 

 

---

문제 출처 👇

https://www.hackerrank.com/challenges/insertion-sort/problem?isFullScreen=true 

Insertion Sort Advanced Analysis | HackerRank

 

참고 👇

https://www.geeksforgeeks.org/difference-between-list-and-array-in-python/

Difference between List and Array in Python - GeeksforGeeks