(c++) 백준 – #5800

전체 코드

#define _CRT_SECURE_NO_WARNINGS      
#define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
#include <iostream>
using namespace std;

void SelectionSort(int Unsorted(), int n) { //n의 숫자가 50으로 그닥 크지않기 때문에 선택정렬을 사용
	for (int i = 0; i < n -1; i++) {
		int min_index = i, temp;
		for (int j = i + 1; j < n; j++) {
			if (Unsorted(min_index) > Unsorted(j)) min_index = j;
		}
		if (i != min_index) {
			SWAP(Unsorted(i), Unsorted(min_index), temp);
		}
	}
} 

int LargestGap(int sorted(), int n) {
	int L = 0, temp;
	for (int i = 0; i < n - 1; i++) {
		if (sorted(i) > sorted(i + 1)) temp = sorted(i) - sorted(i + 1);
		else temp = sorted(i + 1) - sorted(i);

		if (temp > L) L = temp;
	}
	return L;
}

int main(void) {
	int k, n, max, min, gap;
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> n;
		int* score = new int(n);
		for (int i = 0; i < n; i++) cin >> score(i);

		SelectionSort(score, n);
		gap = LargestGap(score, n);

		max = score(n-1);
		min = score(0);

		cout << "Class " << (i + 1) << endl;
		cout << "Max " << max << ", Min " << min << ", Largest gap " << gap << endl;

		delete() score;

	}
	return 0;
}

정렬 기능 선택

#define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )

void SelectionSort(int Unsorted(), int n) { 
	for (int i = 0; i < n -1; i++) {
		int min_index = i, temp;
		for (int j = i + 1; j < n; j++) {
			if (Unsorted(min_index) > Unsorted(j)) min_index = j;
		}
		if (i != min_index) {
			SWAP(Unsorted(i), Unsorted(min_index), temp);
		}
	}
}

정렬 기능을 사용하여 점수를 정렬할 수도 있지만 정렬 확인으로 선택 항목에 대한 나만의 정렬 기능을 만들었습니다.

Python에서는 swap 명령으로 값을 변경하는 것이 쉬웠지만 C 언어에서는 구현해야 했습니다.

위에서 SWAP 매크로를 정의하고 사용했습니다.

*정렬 선택:

1. 주어진 목록에서 최소값을 찾습니다.
2. 이 값을 선행 값으로 바꿉니다(통과).
3. 첫 번째 위치를 제외한 나머지 목록도 같은 방식으로 대체됩니다.

: 선택정렬은 시간복잡도가 O(n**2)이므로 최선의 선택은 아니지만 문제에서 n의 값이 50보다 작다는 조건이 있어서 사용하였다. 그러나 선택 정렬을 사용하여 메모리 측면에서 이점을 확인했습니다.

가장 큰 격차를 찾는 기능

int LargestGap(int sorted(), int n) {
	int L = 0, temp;
	for (int i = 0; i < n - 1; i++) {
		if (sorted(i) > sorted(i + 1)) temp = sorted(i) - sorted(i + 1);
		else temp = sorted(i + 1) - sorted(i);

		if (temp > L) L = temp;
	}
	return L;
}

앞의 숫자와 앞의 숫자의 차이에서 최대값을 찾았습니다. 차이가 음수가 아니도록 차이를 코드화합니다.