[c++] 백준 - 5800번: 성적 통계

5800번: 성적 통계 (acmicpc.net)

전체코드

#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);
		}
	}
}

sort함수를 이용해 쉽게 점수들을 정렬할수도 있었지만 정렬 복습겸 직접 선택정렬 함수를 만들어보았다. 

파이썬에서는 Swap명령어를 이용해 쉽게 값을 바꿀 수 있었지만 c언어에서는 직접 구현하여야 했다. 

상단에 SWAP매크로를 정의해주어 사용하였다. 

    *선택 정렬 :

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

 : 선택정렬은 시간복잡도가 O(n**2) 으로 그다지 최고의 선택은 아니지만 문제에서 n값이 50이하라는 조건이 있었기때문에 사용하였다. 하지만 선택정렬을 사용함으로써 메모리의 관점에서 이점을 봤다. 

 

 

Largest gap을 구하는 함수

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;
}

 

앞뒤 숫자의 차이에서 최댓값을 찾았다.  값의 차이가 음수가 되지않게 코드를 짯다.