[BOJ] 2751번 - 수 정렬하기 2

🧨 문제 출처

문제 출처 : 백준 

문제 난이도 : 실버 5

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

2751번: 수 정렬하기 2

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

문제 그대로 수를 정렬하는 문제였고, 2750번(수 정렬하기) 문제에 비해 정렬할 데이터가 많아져 시간이 부족했다. 2750번은 O(n^2) 정렬로 풀어도 통과됐었지만 2751은 시간초과 오류가 나는 걸 보니 O(nlogn)을 요구하는 문제이다. 퀵 정렬은 데이터 정렬 상태에 따라 n제곱 시간이 걸리기도 해서 안전한 힙정렬을 선택했다. (병합정렬로도 하려고 했는데 이상하게 자꾸 메모리 초과가 난다.. 코드에 문제 없는거 같아서 일단 패스..)

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

vector<int> heapsort(vector<int> L) {
	make_heap(L.begin(), L.end());
	for (auto last = L.end(); last != L.begin(); last--) {
		pop_heap(L.begin(), last);
	}
	return L;
}

int main(void) {
	int n;
	cin >> n;

	vector<int> target(n);

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

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

	// output
	for (int i = 0; i < n; i++) {
		printf("%d\n", result[i]);
	}

	return 0;
}

---

이 문제는..  정말 시간초과가 관건이었다. 예전에 교수님이 cin, cout 말고 scanf 사용하라 하셨는데 그 이유를 오늘 깨달았다.. ^^

scanf 쓰면 vector 쓰기 애매해서 안 썼는데 역시 교수님은 우리한테 이상한걸 알려주진 않으셨다,, 구글링한 정보에 의하면 cin, cout이 scanf, printf 보다 3~5배 더 느리다고 한다. 이번엔 endl을 "\n"으로 바꿔 통과한 것으로 만-족scanf는 다음에 맘 잡고 써본다.. 비주얼 스튜디오에서 이상하게 scanf 오류가 많이 난다.. 이걸 갈아탈수도 없고 참.. (교수님 근데 벡터는 쓰라고 하셨잖아요..)

 

- O(nlogn) 정렬 알고리즘 사용 → 힙정렬, 병합정렬, 퀵정렬 가능

- endl 시간 많이 뺏김 → "\n" 사용하기

- cin, cout 보단 scanf, printf 쓰기

- 시간초과 오류 너무 많이 뜸