[백준] 2751번 : 수 정렬하기 2 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2751번: 수 정렬하기 2

 

1. 문제 설명

2. 풀이과정

해당 문제는 프로그램 실행 시간이 최대한 적게 걸리도록 소스코드를 작성하는 것이 관건이다.

하여 정렬 알고리즘 중 가장 실행 시간이 적게 걸리는 병합정렬 알고리즘을 사용하여 문제를 해결하였다.

또한 자료구조 중 덱(deque)을 활용하여 병합정렬을 수행하였다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 라이브러리를 불러온다. import sys
2. deque이름으로 collections 라이브러리를 불러온다. from collections import deque
3. 병합 정렬을 해줄 함수를 생성한다. def merge_sort(a)
4. 매개변수로 입력받은 리스트의 길이를 변수에 저장한다. n = len(a)
5. 정렬 결과를 저장할 리스트를 생성한다. result = [ ]
6. 만약 리스트의 길이가 1보다 작으면 그냥 리스트를 반환한다. if (n <= 1): return a
7. 리스트의 중앙을 저장한다. mid = n // 2
8. 매개변수로 입력받은 리스트의 처음부터 중앙까지 원소들을 다시 병합 정렬하고 그 결과를 덱(deque) 형태로 저장한다. g1 = deque(merge_sort(a[:mid]))
9. 매개변수로 입력받은 리스트의 중앙부터 끝까지 원소들을 다시 병합 정렬하고 그 결과를 덱(deque) 형태로 저장한다. g2 = deque(merge_sort(a[mid:]))
10. 병합 정렬한 두 덱(deque)이 공백이 될 때까지 반복한다. while (g1 and g2)
11. 왼쪽 병합 정렬의 원소가 오른쪽 병합 정렬의 원소보다 작으면 결과에 작은 값을 추가한다. result.append(g1.popleft())
12. 반면 오른쪽 병합 정렬의 원소가 더 작으면 결과에 더 작은 값을 추가한다. else: result.append(g2.popleft())
13. 왼쪽 병합 정렬이 공백이 될 때까지 원소를 모두 결과에 추가한다. while (g1): result.append(g1.popleft())
14. 오른쪽 병합 정렬이 공백이 될 때까지 원소를 모두 결과에 추가한다. while (g2): result.append(g2.poplef())
15. 병합 정렬한 결과를 반환한다. return result
16. 정렬할 리스트의 원소 개수를 입력받는다. N = int(sys.stdin.readline())
17. 각 원소를 저장할 리스트를 생성한다. li = [ ]
18. 입력받은 원소의 개수만큼 반복하여 for i in range(N)
19.  각 원소를 입력받아 num = int(sys.stdin.readline())
20. 리스트에 추가한다. li.append(num)
21. 리스트를 병합 정렬한 결과를 하나씩 추출하여 출력한다. for i in merge_sort(li): print(i)

반응형

3. 소스코드

import sys
from collections import deque

def merge_sort(a):
    n = len(a)
    result = []

    if (n <= 1):
        return a

    mid = n // 2

    g1 = deque(merge_sort(a[:mid]))
    g2 = deque(merge_sort(a[mid:]))

    while (g1 and g2):
        if g1[0] < g2[0]:
            result.append(g1.popleft())
        else:
            result.append(g2.popleft())

    while (g1):
        result.append(g1.popleft())

    while (g2):
        result.append(g2.popleft())

    return result

N = int(sys.stdin.readline())
li = []

for i in range(N):
    num = int(sys.stdin.readline())

    li.append(num)

for i in merge_sort(li):
    print(i)