선택 정렬(Select-sort) with Python

📖 문제 설명

• 문제 : https://www.acmicpc.net/problem/23881 오늘도 서준이는 선택 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. *N*개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 선택 정렬로 배열 A를 오름차순정렬할 경우 *K* 번째 교환되는 수를 구해서 우리 서준이를 도와주자. 크기가 *N*인 배열에 대한 선택 정렬 의사 코드는 다음과 같다.
  

selection_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
    for last <- N downto 2 {
        A[1..last]중 가장 큰 수 A[i]를 찾는다
        if (last != i) then A[last] <-> A[i]  # last와 i가 서로 다르면 A[last]와 A[i]를 교환
    }
}

• 입력
  • 첫째 줄에 배열 A의 크기 *N*(5 ≤ *N* ≤ 10,000), 교환 횟수 *K*(1 ≤ *K* ≤ N)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
    

• 출력
  • *K 번째 교환되는 두 개의 수를 작은 수부터 한 줄에 출력한다. 교환 횟수가 `K* 보다 작으면 -1`을 출력한다.

💡 요구사항 분석

• 선택 정렬 알고리즘으로 풀기 위해 선택정렬에 대해 알아봅니다.

선택정렬이란 ?

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

선택 정렬 코드

import sys

n = int(sys.stdin.readline())
arr = []

for i in range(n):
    arr.append(int(sys.stdin.readline()))

for i in range(n - 1):
    minValue = i
    for j in range(i + 1, n):
        if arr[minValue] > arr[j]:
            minValue = j
    arr[i], arr[minValue] = arr[minValue], arr[i]

for i in arr:
    print(i)

첫 번째 루프 (for i in range(n - 1))

• i는 현재 정렬할 위치를 가리킵니다. 이 위치부터 시작해서 가장 작은 값을 찾아냅니다.

  초기인덱스 minValue = i

• 현재 위치 i를 가장 작은 값의 위치로 가정합니다.

두 번째 루프 `(for j in range(i + 1, n)):`

• j는 i+1부터 배열의 끝까지 순회하며, 더 작은 값을 찾기 위해 비교합니다.

`if arr[minValue] > arr[j]: minValue = j:`

• 현재 minValue 위치의 값이 j 위치의 값보다 크다면, minValue를 j로 업데이트합니다. 즉, 더 작은 값을 발견하면 minValue를 갱신합니다.

`arr[i], arr[minValue] = arr[minValue], arr[i]:`

• i 위치에 있는 값과 minValue 위치에 있는 값을 교환합니다. 이를 통해 i 위치에 가장 작은 값이 오도록 합니다.

🧑‍💻코드풀이

import sys

n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

answer = []
for i in range(n - 1, 0, -1):
    indexMax = i
    for j in range(i - 1, -1, -1):
        if arr[indexMax] < arr[j]:
            indexMax = j

    if arr[indexMax] != arr[i]:
        k -= 1
        if k <= 0:
            answer.append(arr[indexMax])
            answer.append(arr[i])
            break
		    arr[indexMax], arr[i] = arr[i], arr[indexMax]

if k > 0:
    print(-1)
else:
    answer.sort()
    print(answer[0], answer[1])

• 배열을 뒤에서 탐색하는 선택정렬입니다.
• 교환이 이루어 지면 k -= 1 을 통해 카운팅을 합니다.
• k 가 0 일경우 반복문을 종료하고 정답을 리턴합니다.
• 만약 k 가 0이 아닐 경우 -1 을 출력합니다.
• 마지막 정답을 출력할 때에는 작은 수가 앞에와야 하기 때문에 정렬 후 정답을 출력합니다.