[백준] 23968, 23969 알고리즘 수업 - 버블 정렬 - C

 

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

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

 

---

 

(23968) 버블 정렬을 수행하는 과정에서,  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 = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(&arr[j], &arr[j + 1], &cnt);
				if (cnt == k) {
					printf("%d %d", arr[j], arr[j + 1]);
					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문은 사이클을 반복시켜 주는 반복문이고, 내부 for문은 한 사이클 내에서

두 수를 비교해 큰 값이 오른쪽으로 오게 한다.

이때 두 값의 위치를 변경하는 함수로 swap함수를 만들어 사용했는데, swap함수에서는 cnt값을 받아

1씩 증가시킴으로써 교환이 몇 번 일어났는지 알 수 있게 한다.

또한 이 cnt값이 k값과 일치한다면, 문제에서 요구하는 k번째 교환되는 두 수를 알 수 있다.

---

 

23969번 문제는 앞서 설명했던 문제에서 k번째 교환되는 두 수를 출력하는 것이 아니라

k번째 교환된 후의 배열을 출력하는것이다.

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

 

if문 부분을 이렇게 바꾸어서 배열을 출력해 주면 된다.

---

 

사실 코드 중간에 return을 넣는 것을 좋아하지 않지만, 해당 문제에서는 return을 사용하는 것이

코드가 간결해진다고 생각해 사용하였다..

---