백준 알고리즘(파이썬) - 2751번

수 정렬하기 2

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

2751번: 수 정렬하기 2

이전에 풀었던 수 정렬하기 문제와 다를 것이 없다고 생각했다. 그런데 이 문제는 매우 많은 개수(1 ≤ N ≤ 1,000,000)의 데이터를 입력받기 때문에 2초의 제한시간을 초과하지 않는 것이 중요했다.

선택정렬의 경우는 시간복잡도가 O(n²)이고 병합정렬은 시간복잡도가 O(nlogn)이니까 병합정렬로 정렬 방법을 바꿔서 시도해봤다.

 

병합정렬은 그룹을 작게 나눈 다음 합칠 때 순서에 맞게 합치는 방법을 반복하는 정렬방법이다.

아래 그림을 보면 쉽게 이해할 수 있다. 

 

(병합정렬, 시간초과)

import sys
 
def merge_sort(group):
    n = len(group)
    if n <= 1:
        return
 
    # 그룹을 반으로 나눈다
    mid = n//2
    group1 = group[:mid]
    group2 = group[mid:]
    # 재귀적으로 병합 정렬을 수행한다
    merge_sort(group1)
    merge_sort(group2)
 
    # 정렬한다
    idx, idx1, idx2 = 0, 0, 0 # 그룹전체 인덱스, 그룹1 인덱스, 그룹2 인덱스
    while idx1 < len(group1) and idx2 < len(group2):
        if group1[idx1] < group2[idx2]:
            group[idx] = group1[idx1]
            idx1 += 1
        else:
            group[idx] = group2[idx2]
            idx2 += 1
        idx += 1
    
    # 그룹에 남아있는 원소를 넣는다
    while idx1 < len(group1):
        group[idx] = group1[idx1]
        idx1 += 1
        idx += 1
    while idx2 < len(group2):
        group[idx] = group2[idx2]
        idx2 += 1
        idx += 1
 
# 수를 입력받는다
N = int(sys.stdin.readline())
numbers = [int(sys.stdin.readline().rstrip()) for _ in range(N)]
merge_sort(numbers)
 
# 수를 출력한다
for num in numbers:
    print(num)

잘 돌아가는건 맞는데 시간초과였다. 내가 할 수 있는 시간단축 방법은 input()대신 sys.stdin.readline()를 쓰는 것이었는데 시간제한안에 불가능해서 인터넷에서 다른 방법을 찾아보았다.

 

(성공)

import sys
N = int(input())
numbers = []
for _ in range(N):
    numbers.append(int(sys.stdin.readline()))
for i in sorted(numbers):
    sys.stdout.write(str(i)+'\n')

파이썬 내장함수인 sorted()를 사용한 방법이다. 나는 함수를 쓰지 않고 직접 구현하는 방법을 찾았는데, 찾다가 이렇게 작성한 사람을 발견했다. 이 코드를 작성한 사람은 이미 파이썬 기본 정렬함수가 잘 만들어져 있어서 굳이 더 좋은 방법을 사용할 필요가 없다고 생각했다는데 그말을 듣고보니 빠르고 쉬운 방법이 있는데 굳이 느린 파이썬으로 고생할 필요가 없겠다고 생각했다. 

코드를 작성해서 문제를 해결하는 이유는 내가 완벽하게 방법에 대해 이해하고, 작성하기 위함이 아닌 좋은 도구를 이용해 문제를 빠르게 해결하기 위함임을 다시 한 번 느꼈다.

 

 

참고한 사이트

https://memostack.tistory.com/27

병합 정렬 (Merge Sort) 알고리즘 (with Python3)

 

https://chancoding.tistory.com/19

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