[알고리즘 풀이] 2751번 | 수 정렬하기 2 | c++

문제 보기

https://www.acmicpc.net/problem/2751

 

 

 

입력 개수를 받고, 입력받은 숫자들을 오름차 순으로 정렬하면 되는 문제입니다.

---

들어가며

바보짓을 해서... 시간을 좀 많이 잡아먹었던 친구입니다. 어떤 바보짓이었는지를 말하자면,

문제를 보면 개수가 백만 개가 주어진다고 쓰여있습니다.

백준 문제를 그래도 50개 정도를 풀었었는데, C#으로 했을 때 제 경험상 숫자가 이렇게

크게 주어진다면 기본으로 주어지는 함수로는 시간초과가 떴었습니다.

이번에도 마찬가지 일거라고, c++의 sort도 그럴 거 같아서 이왕 하는 거 직접 정렬 알고리즘을

배우고 구현해 보자 라는 마음으로 문제 풀이를 시작했습니다.

 

겪은 시행착오, 깨달은 것

여러 가지 정렬 알고리즘을 정리한 자료를 봤는데,

힙 정렬이 시간은 빠르지만, 너무 어려워 보였고, 그나마 빠르고 쉬워 보이는

퀵 정렬을 하기 시작했습니다. 이미지로 잘 정리해 둔 블로그와,

이미 정리된 코드를 가끔 참고하면서 두 시간 동안 구현했습니다.

 

참고했던 블로그들

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

https://east-star.tistory.com/10

정렬 알고리즘(Sorting Algorithm) 정복하기 - with JS

 

사실 두 번째 블로그 글의 코드랑 똑같습니다...

코드는 잠깐 보고, 이미지만 보면서 1시간 동안 직접 만들었는데... 정렬이 아예 되지 않아 30분 동안

두 번째 블로그의 코드를 보며 조금씩 비슷하게 수정했습니다. 그럼에도 정렬은 되지 않았습니다.

그래서 30분 동안 왜 안되는지.. 고민을 해보다 혹시 몰라 SortingOrder의 arr 형식을 기본에서

사진과 같이 참조형식으로 바꾸었습니다. 바로 되는 겁니다..

 

C#에서는 클래스는 자동으로 힙에 들어가 참조 형식으로 됐기 때문에, c++에서 백터는

클래스라는 점을 듣고, 자동으로 참조가 될 줄 알았던 것이었죠.

하지만 c++은 직접 할당해주지 않으면 되지 않았던 것이고, 그 때문에 변하지 않았던 겁니다.

이 점 하나 때문에 한 시간은 잡아먹었습니다.

이제 이것만큼은 나중가도 까먹지 않고 기억하지 않을까 싶습니다.

 

드디어 되는 것을 확인하고 백준에 제출했지만.. 시간초과가 뜨고 실패하였습니다.

그러고 나서 좌절에 빠지고, 인터넷 검색을 해보았습니다.

아... 그냥 c++ sort()로 해결이 되는 문제였습니다.

 

알고 보니 퀵 정렬 알고리즘은 평범, 최선에서는 빠르지만, 최악의 상황에서 느린 게 문제인

알고리즘이었습니다. 하지만 sort함수는 퀵 정렬 알고리즘을 바탕으로 최악의 상황도

빠르게 나오게 만든 함수로, 웬만한 상황에서 sort가 다 된다고 합니다.

이 점 또한 나중가도 까먹지 않고 기억할 수 있을 거 같습니다.

 

---

 

코드 풀이

int num[1000000];

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

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

	sort(num, num + n);

	for (int i = 0; i < n; i++) {
		cout << num[i] << "\n";
	}
}

진짜 별거 없습니다. 개수 제한만큼 배열 선언해 두고,

개수받은 만큼 입력받고 sort 써주고 다시 출력 이게 답니다.

 

이때 깨달은 거 한 가지 더.

endl은 시간초과가 떴습니다. 찾아보니

버퍼를 지우면서 다음 줄로 넘기는 거라 느려서 탈출문자로 써야 빨라지는 점이었습니다.

이건 나중 가서 다른 문제 풀 때도 계속 나오는 중요한 점 중 한 가지였습니다.

---

마치며

사실 알고리즘 풀이 블로그 치고는 사담이 많고, 코드 풀이가 적은 거 같습니다.

개인적으로 c++로 처음 알고리즘을 풀어보며 2시간 걸리면서 하고 싶은 말도 많았고,

문제도 sort를 씀으로써 굉장히 쉬웠기에 그랬던 거 같습니다. 다음부턴 코드풀이에 좀 집중하면서

써보도록 하겠습니다.