[백준] 23881, 23882 알고리즘 수업 - 선택 정렬 - C

 

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

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

 

---

 

(23881) 선택 정렬을 수행하는 과정 중에서, k번째로 교환되는 두 수를 출력하면 되는 간단한 문제이다.

선택정렬은 최솟값을 찾아 정렬하는 방식을 사용한다고 생각하고 있었는데, 해당 문제는 최댓값을 찾아

정렬하는 방식을 쓰고 있기 때문에 문제를 잘 읽어 볼 필요가 있는 것 같다.

 

#include <stdio.h>
#include <stdlib.h>

void swap(int* a, int* b, int* cnt);

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	int* arr = malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	int cnt = 0;
	for (int i = n-1; i > 0; i--) {
		int max_idx = i;
		for (int j = i-1; j >= 0; j--) {
			if (arr[j] > arr[max_idx]) {
				max_idx = j;
			}
		}
		if (max_idx != i) {
			swap(&arr[i], &arr[max_idx], &cnt);
			if (cnt == k) {
				printf("%d %d", arr[max_idx], arr[i]);
				free(arr);
				return 0;
			}
		}
	}
	printf("-1");
	free(arr);
	return 0;
}
void swap(int* a, int* b, int* cnt) {
	int temp = *a;
	*a = *b;
	*b = temp;
	*cnt += 1;
}

 

이중 for문의 외부 for문에서는 사이클을 반복시켜 준다.

최댓값을 배열의 뒷부분에 놓아야 하기 때문에 i--를 사용했다.

내부 for문에서는 i 미만의 인덱스를 가진 값을 상대로 최댓값을 구한다.

max_idx값이 바뀐 경우에만 교환을 해야 하기 때문에 if문을 사용했다.

---

 

23882번 문제에서 출력되어야 하는 값은 교환된 두 수가 아니라 교환된 당시의 배열이다.

if (cnt == k) {
	for (int k = 0; k < n; k++) {
		printf("%d ", arr[k]);
	}
	free(arr);
	return 0;
}

 

아주 약간의 수정만 해준다

---