[BOJ] 2752번 - 세 수 정렬

🧨 문제 출처

문제 출처 : 백준 2752번

문제 난이도 : 브론즈 4

문제 링크 : www.acmicpc.net/problem/2752

2752번: 세수정렬

🧨 알고리즘 선택 및 C++ 코드

세 개의 수를 입력해 오름차순 정렬하는 문제다. 사실상 N개의 수를 입력해 오름차순 정렬하는 것과 별반 다르지 않은 문제인데 왜 브론즈 4인지는 의문이다. 다른 방법으로 더 간단하게 구현하는 방법이 많을 거다. 사실 3개의 수라면 복잡하게 정렬 알고리즘을 따지지 않고 2번 또는 3번만 비교해도 대중소를 가려낼 수 있긴 하다. 정렬 알고리즘 공부하면서 구현한거라 그냥 병합정렬 이용해 풀었다. ^^

#include <iostream>
#include <vector>
using namespace std;

/*
* 세 수의 오름차순 정렬
* merge sort (병합정렬) 이용한 정렬문제
*/

vector<int> merge(vector<int> a, vector<int> b) {
	if (a.size() == 0)
		return b;
	if (b.size() == 0)
		return a;

	// 재귀적 병합과정
	if (a[0] < b[0]) {
		vector<int> target;
		target.push_back(a[0]);
		a.erase(a.begin());
		vector<int> p = merge(a, b);
		target.insert(end(target), begin(p), end(p));
		return target;
	}
	else {
		vector<int> target;
		target.push_back(b[0]);
		b.erase(b.begin());
		vector<int> p = merge(a, b);
		target.insert(end(target), begin(p), end(p));
		return target;
	}
}

vector<int> mergesort(vector<int> L) {
	if (L.size() == 1) {
		return L;
	}

	// 분할 지점(mid) 정해서 left, right로 split
	int mid = L.size() / 2;

	vector<int> left, right;
	for (int i = 0; i < mid; i++) {
		left.push_back(L[i]);
	}
	for (int i = mid; i < L.size(); i++) {
		right.push_back(L[i]);
	}

	// left와 right vector 각각 정렬해서 다시 합치기
	vector<int> result = merge(mergesort(left), mergesort(right));
	return result;
}

int main(void) {
	int n = 3;

	vector<int> target(n);

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

	// sort
	vector<int> result = mergesort(target);

	// output
	for (int i = 0; i < n; i++) {
		cout << result[i] << " ";
	}

	return 0;
}

---

그냥 일반적인 알고리즘 문제 풀다가 이런 정렬 문제 풀려고 하면 많이 당황했을 거 같다. 아직 c++ 구현도 익숙지 않고,,

c++ STL template부터 마스터하기..