[백준 BOJ] 23968번 알고리즘 수업 - 버블 정렬 1 (C++/cpp)

문제 설명

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

23968번: 알고리즘 수업 - 버블 정렬 1

 

 

접근 방법 - 버블 정렬의 원리를 이용한 정렬 문제

백준의 23968번 문제는 버블 정렬에 대한 이해를 묻고 있는 문제이다.

해당 문제는, 입력값에 대하여 버블 정렬을 수행할 시 특정 회차에서 교환되는 숫자 2개를 출력해야 하는 문제이다.

여기서 버블 정렬이란, 인접한 2개 숫자의 크기를 비교해가면서 수행하는 정렬 방법이다.

버블 정렬의 원리를 인지하고 있다면 비교적 무난하게 풀 수 있는 문제로 예상된다.

버블 정렬에 대한 개념이 어색하다면 아래의 설명과 코드를 한번 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 입력값을 저장할 배열(arr)을 전역 변수로 선언한다.

 

2) 배열의 크기(n), 정답을 구하고자 하는 특정 회차(k), 배열값들(arr)을 순차적으로 입력받는다.

 

3) 정렬 회차를 카운팅할 변수 num을 0으로 초기화하여 선언한다.

 

4) 이중 반복문을 통하여 아래의 연산을 취한다. (버블 정렬 수행)

(버블 정렬의 실행 시간은 n^2이기 때문에 n^2만큼 반복문을 수행하게끔 하였다.)

- 현재 탐색값이 다음 탐색값보다 크기가 큰 경우, num에 1을 더하고 2개의 값 순서를 변경하도록 한다.

이때 num의 값이 k와 동일한 경우, 작은 숫자부터 시작하여 2개의 숫자를 출력한 뒤, 즉시 실행 종료한다.

 

5) 만일 4)에서 출력이 수행되지 않았다면, 이는 해당 배열에 대한 버블 정렬이 k회차까지 수행되지 않은 경우이다.

이 경우에는 -1을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 23968번 코드
int arr[10000];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int num = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				num++;
				if (num == k) {
					cout << arr[j + 1] << " " << arr[j] << endl;
					return 0;
				}
				int cnt = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = cnt;
			}
		}
	}
	cout << -1 << endl;
}

 

제출 결과

(2022.03.13 백준 23968번 문제 제출 결과)