[파이썬] 백준 23969 알고리즘 수업 버블 정렬 2

이번 글에서는 버블 정렬(Bubble Sort) 알고리즘을 학습하고,

이를 활용하여 백준 23969번 문제를 Python으로 해결하는 방법을 살펴본다. 🚀

 

1. 버블 정렬(Bubble Sort) 이란?

 

버블 정렬은 서로 인접한 두 개의 값을 비교하여 정렬하는 알고리즘이다.

큰 값이 오른쪽으로 이동하며 거품(Bubble)처럼 밀려나는 과정에서 이름이 유래되었다.

 

🔹 버블 정렬의 특징

• 시간 복잡도: 최선 O(n), 평균·최악 O(n²)
• 장점: 구현이 단순
• 단점: 효율이 낮아 큰 데이터 정렬에는 적합하지 않음

🔹 버블 정렬 과정

예제 배열: [7, 2, 0, 1, 5, 6, 4]

 

1️⃣ 첫 번째 패스 (가장 큰 값이 끝으로 이동)

[7, 2, 0, 1, 5, 6, 4]  →  7과 2 비교 → swap
[2, 7, 0, 1, 5, 6, 4]  →  7과 0 비교 → swap
[2, 0, 7, 1, 5, 6, 4]  →  7과 1 비교 → swap
[2, 0, 1, 7, 5, 6, 4]  →  7과 5 비교 → swap
[2, 0, 1, 5, 7, 6, 4]  →  7과 6 비교 → swap
[2, 0, 1, 5, 6, 7, 4]  →  7과 4 비교 → swap
[2, 0, 1, 5, 6, 4, 7]  →  7이 최종 위치

 

2️⃣ 두 번째 패스 (그다음 큰 값이 오른쪽으로 이동)

[2, 0, 1, 5, 6, 4, 7]  →  2와 0 비교 → swap
[0, 2, 1, 5, 6, 4, 7]  →  2와 1 비교 → swap
[0, 1, 2, 5, 6, 4, 7]  →  2와 5 비교 → pass
[0, 1, 2, 5, 6, 4, 7]  →  5와 6 비교 → pass
[0, 1, 2, 5, 6, 4, 7]  →  6과 4 비교 → swap
[0, 1, 2, 5, 4, 6, 7]

 

3️⃣ 세 번째 패스 (남은 정렬 완료)

[0, 1, 2, 5, 4, 6, 7]  →  5와 4 비교 → swap
[0, 1, 2, 4, 5, 6, 7]  →  정렬 완료

 

2. 백준 23969번 문제 설명

 

🔗 문제 링크: 백준 23969 - 알고리즘 수업: 버블 정렬 2

백준 23969 버블 정렬

📌 문제 요구사항

• N: 배열 A의 크기 (5 ≤ N ≤ 10,000)
• K: K번째 교환이 발생한 직후의 배열을 출력 (1 ≤ K ≤ N²)
• 만약 K번째 교환이 발생하지 않으면 -1을 출력

3. 버블 정렬 구현 및 교환 과정 분석

 

🔹 정렬 진행 과정

배열 [4, 6, 5, 1, 3, 2]을 버블 정렬로 정렬하며 교환이 발생한 횟수를 확인한다.

 

소스 내 변경 이력

 

1️⃣ 10번째 교환이 발생한 후 배열 상태

1 3 2 4 5 6

 

2️⃣ 12번째 교환이 발생하지 않으면 -1 출력

 

4. Python 코드 구현

import sys

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

def bubble_sort(lst, K):
    cnt = 0  # 교환 횟수 카운트

    # 버블 정렬 수행
    for i in range(len(lst), 0, -1):
        for j in range(i - 1):
            # 두 수 비교 후 정렬
            if lst[j] > lst[j + 1]:
                cnt += 1
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

                # K번째 교환이 발생하면 즉시 출력 후 종료
                if cnt == K:
                    print(*lst)
                    return

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

# 함수 실행
bubble_sort(A, K)

 

5. 예제 입력 & 출력

 

✅ 예제 1

입력:
6 10
4 6 5 1 3 2

출력:
1 3 2 4 5 6

 

✅ 예제 2

입력:
6 12
4 6 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(len(lst), 0, -1):
    for j in range(i - 1):

• i: 현재 탐색하는 배열 크기 (뒤쪽 정렬된 부분 제외)
• j: 인접한 두 값 비교

🔹 값이 크면 swap + 교환 횟수 증가

if lst[j] > lst[j + 1]:
    cnt += 1
    lst[j], lst[j + 1] = lst[j + 1], lst[j]

• cnt: 교환 횟수
• lst[j] > lst[j + 1]이면 swap

🔹 K번째 교환이 발생하면 즉시 출력 후 종료

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

 

🔹 K번 교환이 일어나지 않으면 -1 출력

print(-1)

 

7. 마무리

 

이번 글에서는 버블 정렬(Bubble Sort) 알고리즘을 이해하고,

백준 23969번 문제를 Python으로 해결했다. 🚀

 

📌 정리

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

✅ K번째 교환이 발생하면 해당 배열 출력

✅ K번째 교환이 발생하지 않으면 -1 출력