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

✅ 백준 문제 링크: 백준 23899번 - 선택 정렬 5

백준 23899 선택 정렬5

1. 선택 정렬(Selection Sort) 알고리즘

 

선택 정렬은 리스트에서 최대값을 찾아 맨 뒤로 보내는 방식으로 정렬하는 알고리즘이다.

 

✔ 선택 정렬 과정

1. 주어진 리스트에서 최대값을 찾는다.
2. 해당 값을 맨 뒤에 위치한 값과 교환(swap)한다.
3. 위 과정을 반복하여 리스트를 정렬한다.

다음은 예제 배열 [3, 1, 2, 5, 4]을 선택 정렬로 정렬하는 과정이다.

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

 

2. 문제 해결 방법

 

이 문제에서는 단순히 정렬을 수행하는 것이 아니라, 선택 정렬 과정 중 배열 A가 배열 B와 동일한 상태가 되는지 확인해야 한다.

 

✔ 해결 과정

1. 배열의 끝부분부터 반복하며 선택 정렬을 수행한다.
2. 정렬 중간 과정에서 배열 A가 배열 B와 동일하면 1을 출력하고 종료한다.
3. 끝까지 정렬했음에도 배열 A가 배열 B와 같지 않다면 0을 출력한다.

3. 선택 정렬을 이용한 풀이 코드

import sys

# 배열 A, B의 크기 N 입력받기
N = int(sys.stdin.readline())

# 배열 A의 원소 입력받기
A = list(map(int, sys.stdin.readline().rsplit()))

# 배열 B의 원소 입력받기
B = list(map(int, sys.stdin.readline().rsplit()))

# 선택 정렬 함수 정의
def selection_sort(lst, cmpLst):
    lng = len(lst)

    # 1. 배열의 끝부분부터 반복하며 정렬 수행
    for i in range(lng - 1, 0, -1):
        # 2. 정렬 과정 중 비교 리스트(B)와 동일하면 1 출력 후 종료
        if lst == cmpLst:
            print(1)
            return
        
        last = i
        # 3. 최대값을 찾기
        for j in range(i - 1, -1, -1):
            if lst[j] > lst[last]:
                last = j
        
        # 4. 최대값을 마지막 위치와 swap
        if last != i:
            lst[i], lst[last] = lst[last], lst[i]
            
            # 5. swap 후 비교 리스트(B)와 동일하면 1 출력 후 종료
            if lst == cmpLst:
                print(1)
                return

    # 6. 끝까지 비교 리스트(B)와 같아지지 않으면 0 출력
    print(0)

# 선택 정렬 함수 호출
selection_sort(A, B)

 

4. 예제 테스트

 

✔ 입력 예시 1

5
3 1 2 5 4
2 1 3 4 5

 

✔ 출력 예시 1

1

📌 설명:

선택 정렬을 수행하는 과정 중 배열 A가 배열 B와 동일한 상태가 되는 순간이 존재하므로 1을 출력한다.

 

✔ 입력 예시 2

5
3 1 2 5 4
1 3 2 4 5

 

✔ 출력 예시 2

0

📌 설명:

선택 정렬을 끝까지 수행해도 배열 A가 배열 B와 동일한 상태가 되는 순간이 없으므로 0을 출력한다.

 

5. 마무리

 

이 문제에서는 선택 정렬을 수행하면서 특정 상태(B)와 일치하는지 확인하는 것이 핵심이다.

🔹 최대값을 찾고, 이를 맨 뒤로 보내는 선택 정렬 방식을 적용해야 한다.

🔹 정렬 과정 중 배열이 목표 배열과 같아지는 순간을 감지하여 빠르게 종료할 수 있도록 최적화했다.