[파이썬] 백준 23881 알고리즘 수업 선택 정렬1

이번 글에서는 선택 정렬(Selection Sort) 알고리즘을 학습하고,

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

 

1. 선택 정렬(Selection Sort)이란?

 

📌 개념

 

선택 정렬은 배열에서 최소값(또는 최대값)을 찾아 정렬하는 방식이다.

정렬이 완료될 때까지 이 과정을 반복하여 배열을 정렬한다.

 

🔹 선택 정렬의 특징

• 시간 복잡도: O(n²)

• 장점: 코드가 단순하여 구현이 쉬움

• 단점: 성능이 낮아 큰 데이터 정렬에는 부적합

 

🔹 정렬 방식

• 오름차순 정렬: 최소값을 찾아 맨 앞과 교환

• 내림차순 정렬: 최대값을 찾아 맨 뒤와 교환

 

2. 선택 정렬 예제 (오름차순 정렬)

 

다음과 같은 리스트가 있다고 보자.

A = [3, 1, 2, 5, 4]

 

이 리스트를 선택 정렬하면 다음과 같이 진행된다.

[3, 1, 2, 5, 4]  → 최소값 1, 0번 index와 swap  
[1, 3, 2, 5, 4]  → 최소값 2, 1번 index와 swap  
[1, 2, 3, 5, 4]  → 최소값 3, 2번 index에 있으므로 pass  
[1, 2, 3, 5, 4]  → 최소값 4, 3번 index와 swap  
[1, 2, 3, 4, 5]  → 정렬 완료 ✅

 

3. 백준 23881번 문제 설명

 

🔗 문제 링크: 백준 23881 - 알고리즘 수업: 선택 정렬 1

백준 23881 선택정렬

📌 문제 요구사항

• N: 배열 A의 크기 (5 ≤ N ≤ 10,000)
• K: K번째 교환된 두 개의 수를 출력 (1 ≤ K ≤ N)
• K번째 교환이 발생하지 않으면 -1을 출력

4. 백준 23881번 선택 정렬 로직 분석

 

백준 문제에서는 최소값이 아니라 최대값을 찾아서 뒤쪽과 교환하는 방식을 사용한다.

 

선택 정렬 (최대값을 뒤로 이동시키는 방식)

[3, 1, 2, 5, 4]  → 최대값 5, 4번 index와 swap  
[3, 1, 2, 4, 5]  → 최대값 4, 3번 index에 있으므로 pass  
[3, 1, 2, 4, 5]  → 최대값 3, 2번 index와 swap  
[2, 1, 3, 4, 5]  → 최대값 2, 1번 index와 swap  
[1, 2, 3, 4, 5]  → 정렬 완료 ✅

 

5. Python 코드 구현

 

(1) 시간 초과 발생 코드 (비효율적인 방식)

#시간초과 발생한 코드
import sys
#배열 A의 크기 N 과 교환횟수 K 를 입력받는다.
N, K = list(map(int, sys.stdin.readline().rsplit()))
#배열 A의 원소들을 입력받는다.
lst = list(map(int, sys.stdin.readline().rsplit()))
cnt = 0
breakYN = False

#1.배열의 끝부분부터 반복한다.
for i in range(N-1, 0, -1):
    last = i
    #2.최대값을 찾는다.
    for j in range(i-1, -1, -1):
        if (lst[j] > lst[last]):
            last = j        
    #3.최대값과 swap. 만약 해당 위치가 최대값이라면 pass
    if last != i:
        #리스트 값 스왑
        lst[i], lst[last] = lst[last], lst[i]
        cnt += 1
    #4.교환횟수에 도달하면 break
    if (cnt == K):
        print(lst[last], lst[i])
        breakYN = True
        break
if breakYN == False:
    print(-1)

 

(2) 시간 초과 해결 코드 (함수 활용 최적화)

#선택정렬 알고리즘으로 시간초과 해결
import sys
#배열 A의 크기 N 과 교환횟수 K 를 입력받는다.
N, K = list(map(int, sys.stdin.readline().rsplit()))
#배열 A의 원소들을 입력받는다.
lst = list(map(int, sys.stdin.readline().rsplit()))
#선택정렬 함수
def selection_sort(N):
    cnt = 0    
    #1.배열의 끝부분부터 반복한다.
    for i in range(N-1, 0, -1):
        last = i
        #2.최대값을 찾는다.
        for j in range(i-1, -1, -1):
            if (lst[j] > lst[last]):
                last = j        
        #3.최대값과 swap. 만약 해당 위치가 최대값이라면 pass
        if last != i:
            #리스트 값 스왑
            lst[i], lst[last] = lst[last], lst[i]
            cnt += 1
        #4.교환횟수에 도달하면 break
        if (cnt == K):            
            return (print(lst[last], lst[i]))
    return(print(-1))
#선택정렬 함수 호출
selection_sort(N)

 

6. 예제 입력 & 출력

 

✅ 예제 1

입력:
5 2
3 1 2 5 4

출력:
2 3

 

✅ 예제 2

입력:
5 4
3 1 2 5 4

출력:
-1

 

7. 코드 설명

 

🔹 입력 받기

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

• N: 배열의 크기
• K: K번째 교환이 발생한 두 개의 값 출력
• lst: 정렬할 배열

🔹 선택 정렬 로직 (최대값을 찾아 뒤로 이동)

for i in range(N - 1, 0, -1):
    last = i

• i: 현재 탐색하는 배열 크기 (뒤쪽 정렬된 부분 제외)
• last: 최대값이 있는 위치

🔹 최대값 찾기 & Swap (교환)

for j in range(i - 1, -1, -1):
    if lst[j] > lst[last]:
        last = j

• lst[j] > lst[last]이면 최대값 위치 갱신

🔹 K번째 교환이 발생하면 작은 값부터 출력 후 종료

if cnt == K:
    return (print(lst[last], lst[i]))

 

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

print(-1)

 

8. 마무리

 

이번 글에서는 선택 정렬(Selection Sort) 알고리즘을 이해하고,

백준 23881번 문제를 Python으로 해결해 보았다. 🚀

 

📌 정리

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

✅ K번째 교환된 두 개의 값을 작은 순서대로 출력

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