HackerRank [Sorting] Insertion Sort - Part 1 /알고리즘 해커랭크

---

문제주소 : https://www.hackerrank.com/challenges/insertionsort1/problem?h_r=next-challenge&h_v=zen

난이도 : Easy
성공률 : 87.32%

 

문제 : 정렬되어있는 배열에서 가장 마지막 인덱스에 특정값을 추가하고
  그 값이 삽입정렬로 자리를 찾아가는 과정을 출력하라
 (단 매번 스왑 하는 방식이 아니라 맨 마지막 값은 가장 마지막에 값이 입력됨)

 

풀이 :
1. 리스트의 가장 마지막 인덱스값을 별도로 저장(nVal)
2. 리스트의 가장마지막 앞의 인덱스부터 별도 저장한 값(nVal)과 비교하여 앞의 인덱스 값이 클 경우 뒤에도 복사
3. 앞의 인덱스 값이 별도 저장 값보다 작을 경우 최초 가장 뒤에 있었던 값을 해당 인덱스 뒷칸에 삽입
4. 맨앞까지 왔는데도 별도 저장 값보다 큰 값이 없을 때를 대비하여 루프 끝난 뒤 별도 저장 값을 맨 앞으로 저장 후 출력 추가

 

답안

#!/bin/python3

import math
import os
import random
import re
import sys

def printList(arr):
    for i in range(0, len(arr)):
        print(arr[i], end='')
        print(' ', end='')    
    print('')


def insertionSort1(n, arr):
    nVal = arr[n-1]
    for i in range(2, n+1):
        if nVal < arr[n-i]:
            arr[n-i+1] = arr[n-i]
            printList(arr)
        else:            
            arr[n-i+1] = nVal
            printList(arr)
            return 0   
    arr[0] = nVal
    printList(arr)
    return 0       
    
    


if __name__ == '__main__':
    n = int(input())

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

    insertionSort1(n, arr)

 

느낀점

삽입 정렬에 대해 오래간만에 remind 할 수 있었다 

실무에서 정렬을 구현해서 쓸 일은 잘 없으니까 자꾸 까먹는 듯..
조금 더 깔끔한 코드로 구현 가능할꺼같은데 피곤해서 여기서 마무리

---