문제
N개의 수가 주어졌을 때, 이를 내림차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
출력
첫째 줄부터 N개의 줄에 내림차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
풀이
풀이 1
퀵 소트를 직접 구현하여 문제를 풀었다.
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int> &list, int left, int right){
int pivot = list[left];
int low = left;
int high = right+1;
while(low <high){
//low가 범위 안에 있고 && 왼쪽 값이 pivot보다 작으면
while(low <right && list[low]>pivot)
low++; //low 오른쪽으로 한칸 이동
//high가 범위 안에 있고 && 오른쪽 값이 pivot보다 크면
while(high>left && list[high]<pivot)
high--; //high 왼쪽으로 한칸이동
//위의 두상황에 어긋나면 값 정렬 변경
if(low <high)
swap(list[low], list[high]);
}
swap(list[left], list[high]);
return high;
}
void quickSort(vector<int> &list, int left, int right){
if(left < right){
int q = partition(list, left, right);
quickSort(list, left, q-1);
quickSort(list, q+1, right);
}
}
int main (){
int n;
cin >> n;
vector<int> numbers;
numbers.assign(n, 0);
//입력
for(int i=0; i<n; i++){
cin >> numbers[i];
}
//연산
quickSort(numbers, 0, n-1);
//출력
for(int i=0; i<n; i++){
cout << numbers[i] << '\n';
}
return 0;
}
그런데 시간초과 실패가 떴다!
quick sort라서 시간 복잡도는 O(nlogn)일텐데 왜 시간초과가 나왔을까...?
풀이 2
이번에는 lib에 있는 sort함수를 사용하여 풀었다.
찾아보니 sort()또한 퀵 정렬과 같은 O(nlogn)의 시간 복잡도를 가진 함수라고 하는데, 그렇다면 1번 풀이가 timeout이 왜 됐는지 더욱 이해가 안간다...
찾아보니 해당 함수는 퀵 소트를 기반으로 heap sort와 insertion sort를 섞은 방식으로 최악의 경우 n^2의 시간 복잡도를 가지는 퀵 소트와는 달리, 최악의 경우에도 nlogn을 보장하는 정렬 알고리즘이라고 한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> numbers;
//입력받기
while(n--){
int num;
cin >> num;
numbers.push_back(num);
}
//내림차순으로 정렬하기
sort(numbers.begin(), numbers.end(), greater<int>());
//출력
for(int i:numbers){
cout << i <<'\n';
}
}역시 내장 정렬을 사용하니 시간 초과가 안뜨고 잘 맞는다.
풀이 3
바킹독의 코드를 참고했다.
딱 처음에 봤을 때 읭?? 싶었다.
sort 함수도 사용하고 있지 않다. 어디에서 정렬이 일어나는걸까?
바킹독의 코드이다.
// Authored by : heheHwang
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/7a7deeedae3b4177a1ed53482685bf15
#include <bits/stdc++.h>
using namespace std;
const int MXN = 2'000'000; //왜 2000000일까? 문제에 주어진 개수는 1,000,000이 최대인데..? > 문제 조건에 절댓값이 1,000,000보다 작거나 같은 정수이기 때문에 공간은 2배로 필요하다!!!
const int HALF = MXN / 2;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
vector<bool> isnum(MXN + 2); //2,000,002개의 0(false)로 초기화 된 인덱스 생성
int N, t;
cin >> N; //입력받을 수의 개수를 입력받기
while (N--) {
cin >> t; //수 입력받기, 만약 5가 입력되면
isnum[t + HALF] = true; //1,000,005번째 인덱스의 값이 1로 변경됨
}
//위의 과정을 통해서 1,000,000~2,000,000 사이에서 불린 숫자의 인덱스가 true로 변경된다.
//2,000,000부터 0까지 돌면서 해당 인덱스의 값이 true인 것을 출력한다.
//이렇게 되면 시간 복잡도는 O(n)이 된다...! 획기적,,
for (int i = MXN; i >= 0; i--)
if (isnum[i]) cout << i - HALF << '\n';
}
/*
수의 등장 여부만 확인, 인덱스를 0에서부터 시작할 수 있게 1,000,000을 더함.
*/어.. 헤더파일 오류랑 이것저것 계속 오류가 난다.
저번에 정리한다고 삭제한 파일 중에 vscode 관련한게 있었나보다....
위의 코드를 정리해보면,
1. 절댓값이 1,000,000보다 작거나 같은 정수를 저장하기 위해서 2,000,000크기의 배열 공간을 만든다.해당 배열 공간은 모두 false로 초기화되어있다.
2. 입력될 수만큼 입력받는다
3. 입력받은 수에 1,000,000을 더해서 (-1,000,000이 0번째 인덱스이므로) 해당 인덱스의 값을 true로 변경한다.
4. 내림차순이므로 가장 큰 인덱스 (MXN)부터 0순서로 1,000,000을 빼서 출력한다.
결국 정렬문제이지만, 결과적으로 정렬 알고리즘은 사용하지 않는 풀이 방식이었다!
시간 복잡도는 입력받은 N의 개수만큼만 돌기 때문에 O(N)이 되기 때문에 그 어떤 정렬 알고리즘보다 시간복잡도가 좋다. 하지만 입력받은 개수가 아니라 수의 범위만큼의 공간이 필요하다.
