[BOJ] 2751. 수 정렬하기 2 (Python, C)

• 코딩 초보. 구현을 목표로 하였기에 비효율적일 수 있습니다.

---

2751. 수 정렬하기 2 

 

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

---

1.Python

 

n=int(input())
num=[]
for i in range(n):
    k=int(input())
    num.append(k)

num.sort(reverse=False)
for i in range(n):
    print(num[i])

sort()를 사용하면 편하다. 그런데 Python3로 제출했을때 시간초과가 뜨는 문제가 있었다. 이럴 경우 PyPy3로 제출하면 시간초과 문제는 해결된다는 걸 알고 PyPy3로 제출했더니 성공했습니다가 떴다. 

 

Python3는 인터프리터 언어라 처리 속도가 느리다는 단점이 있는데, PyPy3는 이 점을 개선시킨 버전이라고 생각하면 된다.

 

---

2.C

 

합병 정렬이라는 방법으로 문제를 풀 수 있다길래 

합병 정렬에 대해 공부해보는 겸, 합병 정렬 방식으로 구현을 해보았다. 

 

#include <stdio.h>

void merge(int a[],int low,int mid,int high) {
	int answer[1000000]; 
	int i = low;
	int j = mid + 1;
	int k = 0; 
	while (i <= mid && j <= high) {
		if (a[i] <= a[j]) answer[k++] = a[i++];
		else answer[k++] = a[j++]; 
	}
	while (i <= mid) answer[k++] = a[i++];
	while (i <= high) answer[k++] = a[j++];
	k--;

	while (k >= 0) {
		a[low + k] = answer[k];
		k--; 
	}
}

void mergeSort(int a[], int low, int high) {
	int mid;
	while (low < high) {
		mid = (low + high) / 2; 
		mergeSort(a, low, mid);
		mergeSort(a, mid + 1, high);
		merge(a, low, mid, high); 
	}
}

int main() {
	int n;
	int num[1000000]; 
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &num[i]); 
	}

	mergeSort(num, 0, n - 1); 

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

참고한 링크: (https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html)

 

합병 정렬이란, 간단히 말해서 배열 리스트의 크기가 1이 될떄까지 분할하여 분할된 배열끼리 하나씩 크기를 차례차례 비교해가는 것이다. 정렬은 합병 정렬 말고도 힙정렬, 퀵정렬 등등이 있는데 차근차근 공부해봐야겠다.

---