[파이썬] 백준 24052 알고리즘 수업 삽입 정렬 2

백준 24052 알고리즘 수업 - 삽입 정렬 2

백준 24052 삽입정렬

☞ 백준 사이트 : https://www.acmicpc.net/problem/24052

 

삽입정렬 로직

• 주어진 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,
• 자신의 위치를 찾아 삽입하는 정렬.

▶ 삽입정렬 정의와 유사 문제 풀이는 이전 글 참고

[파이썬] 백준 24051 알고리즘 수업 삽입 정렬 1

풀이

1. 배열의 1번 index부터 마지막까지 반복한다.
2. 값을 맨 앞까지 이동하면서 정렬대상인지 판단되면 이동해야 할 index 저장, 나머지 shift
3. 이동해야 할 index가 있다면, 그 자리에 대상 값 저장(insert)
4. K 번 변경이 발생한 직후의 배열 A를 한 줄에 출력

소스 내 값 변경 history

[4, 5, 1, 3, 2]

• 소스 내 while 문 (newItem = 1)
  • [4, 5, 5, 3, 2]
  • [4, 4, 5, 3, 2]
• 소스 내 if 문
  • [1, 4, 5, 3, 2]
• 소스 내 while 문 (newItem = 3)
  • [1, 4, 5, 5, 2]
  • [1, 4, 4, 5, 2]
• 소스 내 if 문
  • [1, 3, 4, 5, 2]
• 소스 내 while 문 (newItem = 2)
  • [1, 3, 4, 5, 5]
  • [1, 3, 4, 4, 5]
  • [1, 3, 3, 4, 5]
• 소스 내 if문
  • [1, 2, 3, 4, 5]

import sys
#배열 A의 크기 N, 저장횟수 K 입력받는다.
N, K = list(map(int, sys.stdin.readline().rsplit()))
#배열 A의 원소들을 입력받는다.
A = list(map(int, sys.stdin.readline().rsplit()))

def insertion_sort(lst, K):
    cnt = 0
    #1.배열의 1번 index 부터 마지막까지 반복한다.
    for i in range(1, len(lst)):
        loc = i - 1
        newItem = lst[i]

        # 이 지점에서 A[1..i-1]은 이미 정렬되어 있는 상태
        #2.값을 맨 앞까지 이동하면서 정렬대상인지 판단되면 이동해야할 index 저장, 나머지 shift
        while (0 <= loc and newItem < lst[loc]):
            cnt += 1
            lst[loc+1] = lst[loc]
            loc -= 1
            #4.K번 변경이 발생한 직후의 배열 A를 한 줄에 출력
            if cnt == K:
                return(print(*lst,sep=" ", end=""))
        #3.이동해야할 index가 있다면, 그 자리에 대상 값 저장(insert)
        if (loc + 1 != i):
            cnt += 1
            lst[loc + 1] = newItem
            #4.K번 변경이 발생한 직후의 배열 A를 한 줄에 출력
            if cnt == K:
                return(print(*lst,sep=" ", end=""))
    #5.변경 횟수가 K보다 작으면 -1을 출력
    return(print(-1))
insertion_sort(A,K)
"""
5 7
4 5 1 3 2
1 3 4 5 5
"""