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

이번 글에서는 삽입 정렬(Insertion Sort) 알고리즘을 학습하고,

이를 활용하여 백준 24052번 문제를 Python으로 해결해본다. 🚀

 

1. 삽입 정렬 (Insertion Sort) 란?

 

삽입 정렬은 배열을 앞에서부터 차례대로 정렬된 부분과 비교하며 자신의 위치를 찾아 삽입하는 정렬 알고리즘이다.

 

🔹 정렬 과정:

1. 배열의 두 번째 요소부터 시작하여 왼쪽의 정렬된 부분과 비교
2. 적절한 위치를 찾아 삽입
3. 모든 요소가 정렬될 때까지 반복

 

🔹 시간 복잡도:

1. 최선 (O(n)): 이미 정렬된 배열일 경우
2. 최악 (O(n²)): 역순 정렬된 배열일 경우

2. 백준 24052번 문제 설명

 

🔗 문제 링크: 백준 24052번 - 알고리즘 수업: 삽입 정렬 2

백준 24052 삽입정렬

📌 문제 요구사항

• N: 배열 A의 크기 (5 ≤ N ≤ 10,000)
• K: 정렬 중 K번째 변경이 일어난 직후의 배열 출력 (1 ≤ K ≤ N²)
• 만약 K번 변경이 일어나지 않으면 -1을 출력

3. 삽입 정렬 구현 및 변경 과정 분석

 

🔹 삽입 정렬 진행 과정

 

배열이 [4, 5, 1, 3, 2]일 때, 정렬 과정에서 변경되는 모습이다.

 

소스 내 변경 이력

 

1️⃣ newItem = 1

[4, 5, 5, 3, 2]
[4, 4, 5, 3, 2]  ← while 문 실행
[1, 4, 5, 3, 2]  ← if 문 실행

 

2️⃣ newItem = 3

[1, 4, 5, 5, 2]
[1, 4, 4, 5, 2]  ← while 문 실행
[1, 3, 4, 5, 2]  ← if 문 실행

 

3️⃣ newItem = 2

[1, 3, 4, 5, 5]
[1, 3, 4, 4, 5]
[1, 3, 3, 4, 5]  ← while 문 실행
[1, 2, 3, 4, 5]  ← if 문 실행

 

🔹 최종 결과:

[1, 2, 3, 4, 5]

 

4. Python 코드 구현

import sys

# 배열 A의 크기 N, 변경 횟수 K 입력받기
N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

def insertion_sort(lst, K):
    cnt = 0  # 변경 횟수 카운트

    # 삽입 정렬 수행
    for i in range(1, len(lst)):
        loc = i - 1
        newItem = lst[i]

        # 왼쪽 정렬된 부분과 비교하며 이동
        while loc >= 0 and newItem < lst[loc]:
            cnt += 1
            lst[loc + 1] = lst[loc]  # 값 이동
            loc -= 1

            # K번째 변경 발생 시 출력 후 종료
            if cnt == K:
                print(*lst)
                return

        # 새로운 위치에 삽입
        if loc + 1 != i:
            cnt += 1
            lst[loc + 1] = newItem

            # K번째 변경 발생 시 출력 후 종료
            if cnt == K:
                print(*lst)
                return

    # 변경 횟수가 K보다 작으면 -1 출력
    print(-1)

# 함수 실행
insertion_sort(A, K)

 

 

5. 예제 입력 & 출력

 

✅ 예제 1

입력:
5 7
4 5 1 3 2

출력:
1 3 4 5 5

 

✅ 예제 2

입력:
5 11
4 5 1 3 2

출력:
-1

 

6. 코드 설명

 

🔹 입력 받기

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

• N: 배열의 크기
• K: K번째 변경 후 배열 출력
• A: 정렬할 배열

🔹 삽입 정렬 로직

for i in range(1, len(lst)):
    loc = i - 1
    newItem = lst[i]

• i: 현재 정렬할 원소의 인덱스
• loc: 비교할 위치 (왼쪽 정렬된 부분)
• newItem: 정렬 대상 값

🔹 왼쪽 요소와 비교하며 위치 찾기

while loc >= 0 and newItem < lst[loc]:
    cnt += 1
    lst[loc + 1] = lst[loc]  # 값 이동
    loc -= 1

• while 문을 통해 왼쪽 요소와 비교하며 자리 이동

🔹 K번째 변경 후 즉시 출력

if cnt == K:
    print(*lst)
    return

• cnt == K이면 배열을 출력하고 함수 종료

🔹 마지막까지 K번 변경이 발생하지 않으면 -1 출력

print(-1)

 

7. 마무리

 

이번 글에서는 삽입 정렬(Insertion Sort) 알고리즘을 이해하고,

백준 24052번 문제를 Python으로 해결해 봤다. 🚀

 

📌 정리

✅ 삽입 정렬은 **O(n²)**의 시간 복잡도를 가짐

✅ K번째 변경이 발생하면 즉시 배열 출력

✅ K번 변경이 발생하지 않으면 -1 출력