[백준 BOJ] 23881번 알고리즘 수업 - 선택 정렬 1 (C++/cpp)

문제 설명

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

23881번: 알고리즘 수업 - 선택 정렬 1

 

 

 

접근 방법 - 선택 정렬 알고리즘 기본 문제

백준의 23881번 문제는 선택 정렬 알고리즘을 이용하여 해결해야 하는 문제이다.

해당 문제는, 선택 정렬을 진행하면서, 입력받은 교환 횟수에서 교환되는 두 숫자를 출력해야 하는 문제이다.

문제에 제시된 선택 정렬은, 맨 끝에서부터 큰 숫자를 차례로 선택하고 배치하며 정렬을 수행하는 알고리즘이다.

자세한 설명은 문제의 의사 코드에 제시되어있으니 꼭 참고해보길 바란다.

필자는 알고리즘의 설명을 따라서 코드를 작성하여 해당 문제를 해결하였다.

정렬 알고리즘에 대해 어색하거나 선택 정렬의 정의를 처음 접하였다면 아래의 설명도 함께 참고해보길 바란다.

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

 

코드의 실행 순서

1) 배열의 크기(n), 교환 횟수(k), 배열의 상태(arr)를 차례로 입력받는다.

 

2) 교환 횟수를 카운팅하는 변수 num을 0으로 초기화하여 선언한다.

 

3) 배열의 끝 부분부터 정렬 알고리즘을 실행한다. 반복문을 실행하면서 아래의 연산을 취한다.

- 배열 번호 i번 아래의 값들 중 최댓값을 구한다. 이때, 배열 번호와 배열값을 각각 함께 별도의 변수에 저장해둔다.

- 위에서 선정된 최댓값과 현재 i번 배열값 크기를 비교한다. 이때 선정된 최댓값이 더 크다면, 두 개의 값 위치를 바꾼다.

 

4) 위 반복문에서 교환이 실행되었을 시, num에 1을 더한다. 그리고 num과 k 값을 비교한다.

만일 두 변수의 값이 같을 시엔, 교환한 두 개의 숫자를 출력한 뒤 실행 종료한다.

(출력할 시, 작은 수부터 출력되게끔 해야 한다.)

 

5) 실행 종료될 때까지 3) ~ 4) 과정을 반복한다.

반응형

 

성공한 코드

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

//백준 23881번 코드
int arr[10000];
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int num = 0;
	for (int i = n - 1; i >= 0; i--) {
		int m = arr[0];
		int max = 0;
		for (int j = 0; j < i; j++) {
			if (m < arr[j]) { 
				m = arr[j];
				max = j; 
			}
		}

		int a, b;
		if (arr[max] > arr[i]) {
			int cnt = arr[i];
			arr[i] = arr[max];
			arr[max] = cnt;
			a = arr[max], b = arr[i];
			num++;
			if (num == k) {
				cout << a << " " << b << endl;
				return 0;
			}
		}
	}

	cout << -1 << endl;
}

 

제출 결과

(2022.03.05 백준 23881번 문제 제출 결과)