[코팅테스트] 백준 #2751 수 정렬하기 (STL 사용)

백준 #2751 수 정렬하기

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

 

버블 정렬 공부하면서 이번 문제는 버블정렬로 풀어야지! 했는데 

계속 시간 초과가 났습니다.

 

분명히 2750 문제랑 똑같았다고 생각했는데 원인을 찾아보니 입력 수가 1,000,000 으로 늘어난 걸 캐치를 못했어요 ㅠㅠ

그래서 오래 걸리는 버블이랑 선택 정렬로 풀어도 #2750은 풀렸는데 #2751은 안풀렸습니다.

 

그래서 이번에는 C++ STL 함수 sort()를 사용했습니다.

"algorithm.h" 에 포함되어 있는 함수이니까 #inlcude <algorithm> 해주세요~

 

Sort() 는 퀵 정렬을 기반으로 힙 정렬과 삽입 정렬이 혼합된 방식으로 구현되어 있다고 하네요.

따라서 O(N^2) 시간 복잡도를 갖는 퀵 정렬과 다르게 O(n log n)을 보장한다고 해요!

 

STL 함수를 잘 활용하여 코테를 푸는 것도 방법이겠어요 

 

참고로 Sort는 기본적으로 오름차순이지만 아래와 같은 방법으로 설정할 수 있습니다.

 

//오름차순

sort(배열 시작, 배열 끝, less<int>()); 

 

//내림차순

sort(배열 시작, 배열 끝, greater<int>()); 

 

 

sort()를 이용해 오름차순 정렬을 구현한 방법은 아래와 같습니다.

 

구현

#include <iostream>
#include <algorithm>
using namespace std;
	int arr[1000000];

int main() {
	/**  버블 정렬  **/
	//옆의 수와 비교하여 작으면 앞으로 보낸다.

	int inputNumber;
	std::cin >> inputNumber;

	for (int i = 0; i < inputNumber; i++) {
		std::cin >> arr[i];
	}

	std::sort(arr, arr + inputNumber);

	for (int k = 0; k < inputNumber; k++) {
		std::cout << arr[k] << "\n";
	}

	return 0;
}

 

마치며

STL 함수 없이 풀다가 계속 메모리 초과나서 좀 답답했는데, 구글링 통해서 해결 방법을 찾았습니다.

앞으로 STL 함수들을 좀 더 많이 이용해서 푸는 시간을 더 줄여봐야겠어요

1일 1문제 하도록  노력해보겠습니다.

 

읽어주셔서 감사합니다 C: