2752번: 세수정렬

2752번: 세수정렬(BOJ C/C++)

사용 언어: C++

문제

동규는 세수를 하다가 정렬이 하고싶어졌다.

숫자 세 개를 생각한 뒤에, 이를 오름차순으로 정렬하고 싶어 졌다.

숫자 세 개가 주어졌을 때, 가장 작은 수, 그 다음 수, 가장 큰 수를 출력하는 프로그램을 작성하시오.

입력

숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다.

출력

제일 작은 수, 그 다음 수, 제일 큰 수를 차례대로 출력한다.

 

첫 번째 풀이

그냥 버블정렬과도 같고 풀이들 중 시간복잡도가 가장 긴 O(n^2) 이다. 물론 지금은 배열의 크기가 작아서 상관없지만 크기가 커지만 이 풀이는 지양적이다.

#include <bits/stdc++.h>
using namespace std;
int arr[4];

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

	for(int i=0;i<3;i++)
		cin>>arr[i];
	for(int i=0;i<2;i++)
		for(int j=0;j<2-i;j++)
			if(arr[j]>arr[j+1])
				swap(arr[j],arr[j+1]);
	for(int i=0;i<3;i++)
		cout<<arr[i]<<' ';

	return 0;
}

 

두 번째 풀이

algorithm 헤더에 있는 min과 max 함수를 사용. 중간 값은 숫자가 세개밖에 없으므로 e=a+b+c-d-f 처럼 단순하게 표현할 수 있다. 이 문제에 최적화된 풀이.

#include <bits/stdc++.h>
using namespace std;
int arr[4];

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

	int a, b, c;
	cin>>a>>b>>c;
 	int d, e, f;
	d = min({a,b,c});
	f = max({a,b,c});
	e = a+b+c-d-f;
	cout<<d<<' '<<e<<' '<<f;

	return 0;
}

 

세 번째 풀이

가장 단순명료한 algorithm 헤더의 sort 함수. 오름차순으로 정렬을 해준다. 또한 시간복잡도도 O(n*logn) 이어서 버블정렬의 O(n^2) 보다는 좋다.

#include <bits/stdc++.h>
using namespace std;
int arr[4];

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

	int arr[4];
    for(int i=0;i<3;i++)
    	cin>>arr[i];
    sort(arr, arr+3);
    for(int i=0;i<3;i++)
 	    cout<<arr[i]<<" ";
	
	return 0;
}

 

느낀 점

현재 c++로 푸는 문제들이 쉬운 편에 속하지만 각 헤더에 있는 함수들을 새로 배워나가는 재미는 있어서 좋다. 그리고 이런 단순한 항목의 문제들은 따로 카테고리를 두지 않고 태그로만 분류하겠다 (예로 이번 문제는 정렬).