[Baekjoon] #23881 알고리즘 수업 - 선택 정렬1

📝 문제

https://www.acmicpc.net/problem/23881

💬 풀이 방법

아이디어

문제의 제목에서도 확인할 수 있듯이 선택 정렬의 개념을 응용하여 해답을 구하는 문제이다.

교환이 발생하는 과정을 확인해야 하기 때문에 교환 횟수를 체크할 변수 cnt를 선언하고, 최종적으로 출력될 값 answer를 선언한다.
루프를 진행하면서 원소의 자리 교체가 이루어지는 경우 cnt + 1을 하여 cnt와 교환 횟수 K가 같아지는 시점에 answer의 값을 변경한다.

알고리즘

1. 배열 A의 크기 N, 교환 횟수 K, 배열 A의 원소를 각각 sys.stdin.readline()을 활용하여 입력받는다.
2. 배열 A의 원소 중 가장 큰 값을 max_item 변수에 저장한다.
3. max_item이 가장 마지막 원소가 아닐 경우, 마지막 원소와 자리를 교환한 뒤 cnt에 1을 더해준다.
4. 정렬된 값을 제외한 배열에서 위의 과정을 반복한다.
5. cnt의 값이 K가 되었을 때, answer의 값을 arr[i], max_item으로 포매팅한다.
   
   

💻 소스코드

import sys

n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
cnt = 0
answer = -1

def selection(arr):
	global cnt, answer

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

		if arr[i] != arr[idx]:
			arr[i], arr[idx] = arr[idx], arr[i]
			cnt += 1

		if cnt == k:
			answer = f'{arr[idx]} {arr[i]}'

	return answer
		

print(selection(arr))