[Beginner][백준] 2751번 : 수 정렬하기 2

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

2751번: 수 정렬하기 2

 

[ 풀이 후기 ]
난이도 : ★☆☆☆ (Beginner)
문제 종류 : Sort
해결 방법 : Merge Sort

 

* 난이도 구분
★☆☆☆ (Beginner) : 알고리즘 적용만으로 해결 가능
★★☆☆ (Advanced) : 알고리즘을 활용하여 구현해야 해결 가능
★★★☆ (Pro) : 알고리즘을 활용한 구현 + 최적화 아이디어로 해결 가능
★★★★ (Expert) : Pro보다 발전된 최적화 아이디어로 해결 가능

 

---

 

문제

 

문제 분석

1. 입력되는 수는 최대 100만개이고, 각각의 수도 100만 이하의 정수이므로, int 변수를 선언하도록 하자. 
2. 100만개의 수를 오름차순으로 정렬하자. 

 

---

 

접근 방법1 : 무작정 비교해서 Sorting (버블 Sort)

입력 받은 N개의 수를 무작정 비교해서 정렬하는 방법으로 해보자. 

 

0번 Index의 수를 1~4 Index 수들과 비교해서, 0번의 수가 더 크다면, 자리를 바꾸는 방식으로 해보자. (버블 Sort)

정렬 결과

1. 5 와 4를 비교한다. 5가 더 크니까 자리를 바꾼다. 
2. 5와 3을 비교한다. 5가 더 크니까 자리를 바꾼다. 
3. ... 
4. 5와 1을 비교한다. 5가 더 크니까 자리를 바꾼다.

 

같은 방식으로 또 해보자. 

정렬 결과

1. 4 와 3을 비교한다. 4가 더 크니까 자리를 바꾼다. 
2. 4와 2를 비교한다. 4가 더 크니까 자리를 바꾼다. 
3. ... 
4. 4와 5을 비교한다. 5가 더 크니까 자리를 바꾸지 않는다.

 

이 과정을 모두 정렬될때까지 반복하면, 비교횟수와 시간복잡도는 다음과 같이 계산할 수 있다. 

5를 기준으로 했을 때 4번 비교,
4를 기준으로 했을 때 4번 비교,
... 
▶ 총 5 * 4 번 비교
▶ O( N * (N-1) )
▶ O(N²)

 

N=5 일때는 O(5²)으로, 시간이 얼마 걸리지 않지만,

위 문제의 경우 N=100만 이므로, O(100만²) 의 시간복잡도를 가지게 된다.

2초 내에 프로그램이 종료되어야 하므로, 이 방법으로는 해결할 수 없다. 

 

※ O(1억) 인 경우 약 1초 걸린다고 판단하면 된다. 

 

 

---

 

접근 방법2 : Merge Sort

위의 방식은 O(N²) 의 시간복잡도 이므로, 문제를 해결할 수 없다. 

O(N log N) 의 시간복잡도를 가지는 Merge Sort로 해결해보자. 

 

Merge Sort의 원리는 아래 포스팅을 참고하세요 :)

[자료구조][정렬][C/C++] Merge Sort (병합정렬)

[자료구조][정렬][C/C++] Merge Sort (병합정렬)

 

 

 

Merge Sort는 아래와 같이 4단계로 나눠서 구현할 수 있다. 

1. base condition : 종료 조건
2. divide & conquer : 중간을 기준으로 나눠서 재귀
3. merge : 나눠졌던 Data를 하나로 합치기 (임시 배열 활용, 아래 코드에서는 trr 배열)
4. copy : 임시 배열의 Data를 원래 배열에 복사 (아래 코드에서는 A 배열)

const int LM = 1000000;
int A[LM + 5], trr[LM + 5];

void mergeSort(int s, int e) {
	if (s >= e) return;	// 1. base condition

	int mid = (s + e) / 2;	// 2. divide & conquer
	mergeSort(s, mid);
	mergeSort(mid + 1, e);

	int i = s, j = mid + 1, k = s;		// 3. merge
	while (i <= mid && j <= e) {
		if (A[i] < A[j]) trr[k++] = A[i++];
		else trr[k++] = A[j++];
	}
	while (i <= mid) trr[k++] = A[i++];		// left쪽 Data가 남은 경우
	while (j <= e) trr[k++] = A[j++];		// right쪽 Data가 남은 경우

	for (i = s; i <= e; i++) A[i] = trr[i];		// 4. copy
}

 

 

이렇게 구현된 mergeSort 함수는 아래와 같이 main에서 호출하면 된다. 

(첫번째 Data를 0번 Index에 저장하는 것이 아닌, 1번 Index에 저장했다.)

mergeSort(1, N);	// Sorting

 

 

이제 main을 포함한 전체 코드를 살펴보자. 

#include <stdio.h>

const int LM = 1000000;
int N;
int A[LM + 5], trr[LM + 5];

void mergeSort(int s, int e) {
	if (s >= e) return;		// 1. base condition

	int mid = (s + e) / 2;	// 2. divide & conquer
	mergeSort(s, mid);
	mergeSort(mid + 1, e);

	int i = s, j = mid + 1, k = s;		// 3. merge
	while (i <= mid && j <= e) {
		if (A[i] < A[j]) trr[k++] = A[i++];
		else trr[k++] = A[j++];
	}
	while (i <= mid) trr[k++] = A[i++];		// left쪽 Data가 남은 경우
	while (j <= e) trr[k++] = A[j++];		// right쪽 Data가 남은 경우

	for (i = s; i <= e; i++) A[i] = trr[i];		// 4. copy
}

int main() {
	scanf("%d", &N);	// N 입력
	for (int i = 1; i <= N; i++) {
		scanf("%d", A + i);		// N개의 수 입력
	}

	mergeSort(1, N);	// Sorting

	for (int i = 1; i <= N; i++)
		printf("%d\n", A[i]);	// 정렬된 수 출력

	return 0;
}

 

---

 

제출 결과

백준 제출 결과