#2751: 수 정렬하기 2
문제:
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력:
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
풀이:
어떤 종류의 정렬을 이용해야 될까 고민 하다가 병합 정렬(Merge Sort)이나 C++ STL에 sort() 함수를 이용할까 고민하다가 간단한 sort() 함수를 먼저 이용해보고 시간 초과로 안풀리면 병합 정렬을 이용할려고 하였다. 최악의 경우에 sort() 함수는 시간 복잡도가 O(N^2)이기 때문이였다.
코드:
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
int n;
cin >> n;
int numbers[n];
for(int i = 0; i < n; i++){
cin >> numbers[i];
}
sort(numbers, numbers+n);
for(int i = 0; i < n; i++){
cout << numbers[i] << '\n'; // '\n' 안쓰면 시관 초과
}
}
핵심 포인트:
이 문제의 핵심 포인트는 답을 출력시 ‘endl’을 이용하는 것이 아닌 ‘\n’을 활용하여 문제를 풀어야 한다. 만약에 ‘endl’을 이용하게 되면 시간 초과로 오답 처리가 된다. 아마 ‘endl’은 std 라이브러리를 한번 거쳐서 출력을 하는 것이라서 시간을 더 사용하는 것인 것 같다. 백준 게시판에서 찾아보니 알고리즘 문제 풀이 할 때는 줄 바꿈을 ‘endl’이 아닌 ‘\n’을 이용하는게 좋다고 한다.
병합정렬 풀이:
코드1:
메모리를 아낄려고 글로벌 변수를 안만들고 계속 sorted[]를 계속 passing하는 식으로 하였지만 메모리에서 큰 차이가 없었음 고로 글로벌 변수를 선언하는 방식이 조금 더 깔끔한 듯
#include <iostream>
using namespace std;
int* merge(int numbers[], int start, int middle, int end, int sorted[]){
int i = start;
int j = middle + 1;
int k = start;
while(i <= middle && j <= end){
//i와 j중 더 큰 것을 sorted[]에 순서대로 비교하면서 넣음
if(numbers[i] <= numbers[j]){
sorted[k] = numbers[i];
i++;
} else{
sorted[k] = numbers[j];
j++;
}
k++;
}
//분할 된 한쪽이 먼저 넣어질 경우 남은 한쪽 데이터 다 넣음
if(i > middle){
for(int temp = j; temp <= end; temp++){
sorted[k] = numbers[temp];
k++;
}
} else{
for(int temp = i; temp <= middle; temp++){
sorted[k] = numbers[temp];
k++;
}
}
//정렬 된 배열 삽입
for(int temp = start; temp <= end; temp++){
numbers[temp] = sorted[temp];
}
return numbers;
}
int* mergeSort(int numbers[], int start, int end, int sorted[]){
if(start < end){
int middle = (start + end)/2;
mergeSort(numbers, start, middle, sorted);
mergeSort(numbers, middle+1, end, sorted);
merge(numbers, start, middle, end, sorted);
}
return numbers;
}
int main(void){
int n;
cin >> n;
int numbers[n];
int sorted[n];
int *random;
for(int i = 0; i < n; i++){
cin >> numbers[i];
}
//random = mergeSort(numbers, 0, n, sorted);
random = mergeSort(numbers, 0, n-1, sorted);
for(int i = 0; i < n; i++){
cout << random[i] << '\n';
}
}
코드 2:
위 코드와 차이점은 글로벌 변수를 이용함으로써 array를 return 할 필요가 없으므로 함수의 return 값이 모두 void이며 변수에 있던 sorted array를 모두 지움. 또한 main 함수에 random도 필요 없어져서 지움.
#include <iostream>
using namespace std;
int sorted[1000000];
void merge(int numbers[], int start, int middle, int end){
int i = start;
int j = middle + 1;
int k = start;
while(i <= middle && j <= end){
//i와 j중 더 큰 것을 sorted[]에 순서대로 비교하면서 넣음
if(numbers[i] <= numbers[j]){
sorted[k] = numbers[i];
i++;
} else{
sorted[k] = numbers[j];
j++;
}
k++;
}
//분할 된 한쪽이 먼저 넣어질 경우 남은 한쪽 데이터 다 넣음
if(i > middle){
for(int temp = j; temp <= end; temp++){
sorted[k] = numbers[temp];
k++;
}
} else{
for(int temp = i; temp <= middle; temp++){
sorted[k] = numbers[temp];
k++;
}
}
//정렬 된 배열 삽입
for(int temp = start; temp <= end; temp++){
numbers[temp] = sorted[temp];
}
}
void mergeSort(int numbers[], int start, int end){
if(start < end){
int middle = (start + end)/2;
mergeSort(numbers, start, middle);
mergeSort(numbers, middle+1, end);
merge(numbers, start, middle, end);
}
}
int main(void){
int n;
cin >> n;
int numbers[n];
int sorted[n];
for(int i = 0; i < n; i++){
cin >> numbers[i];
}
mergeSort(numbers, 0, n-1);
for(int i = 0; i < n; i++){
cout << numbers[i] << '\n';
}
}
|정렬 종류|메모리|시간| |——|—|—| |STL sort()|5804|672| |병합 정렬 코드 1|9712|736| |병합 정렬 코드 2|9716|720|
Leave a comment