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

유형 : 정렬

[예제]

5
5
4
3
2
1

[출력]

1
2
3
4
5

---

1. 내 풀이

import sys

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

for _ in range(N):
    _list.append(int(sys.stdin.readline()))

_list.sort()

for data in _list:
    print(data)

▷ 기본 정렬 라이브러리(sort())를 이용해 쉽게 구할 수 있었다.
▷ input()을 쓰면 시간초과가 나오길래 sys.stdin.readline()으로 수정하였다.

   ▶ input() 함수의 경우 prompt message를 출력하고 개행 문자(\n)를 삭제한 값을 리턴해서 느리다고 한다.

   ▶ 참고 : [Python] Input vs. sys.stdin.readline 차이점?

▷ 퀵정렬로 한번 시도했었는데 시간 초과가 발생했다. (PyPy3에서 하니 메모리 초과)

 

2. 다른 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

 

** 핵심 아이디어
1. 데이터의 개수가 최대 1,000,000개이다.

2. 시간 복잡도 O(NlogN)의 정렬 알고리즘을 이용해야 한다.
- 보통 log₂N를 설정하는데, 여기서 최대 20까지 만들 수 있다. (2^10 ≒1000, N=1000000)
- O(NlogN)으로 작성해야 약 2천만번의 연산 횟수가 가능하다.

3. 고급 정렬 알고리즘(병합/퀵/힙 정렬 등)을 이용해 문제를 해결할 수 있다.
- 퀵 정렬에서 최악의 경우 O(N²)이기 때문에 다른 정렬을 이용하는게 좋다.
4. 또는 파이썬의 기본 정렬 라이브러리를 이용해도 해결가능하다.

5. 메모리가 허용된다면, 되도록 Python 3보다는 PyPy3를 선택해 코드를 제출하자.
- PyPy3가 Python3보다 더 빠르다.

 

2-1. 병합 정렬 이용

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

1) 특징

- 분할 정복(Divide & Conquer) 방식을 이용한다.
- 절반씩 합치면서 정렬한다.

- 시간 복잡도 : O(NlogN)

 

 

2) 진행 과정

- 병합할 때는 리스트의 앞 원소부터 차례대로 채워 넣는다.

 

ex. 5 7 4 8 → 4 5 7 8

① i=0, j=0, k=0

② i=0, j=1, k=1

- i,j가 가리키는 원소 중 작은 원소가 k가 가리키는 곳에 들어간다.

③ i=1, j=1, k=2

 ④ i=2, j=1, k=3

⑤ i=2, j=2, k=4

- 한 쪽 리스트에서 원소를 다 넣었다면 다른 리스트에서 남은 원소를 하나씩 넣는다.

 

** 코드

def merge_sort(array):
    if len(array) <= 1:
    	return array
    
    mid = len(array) // 2
    left= merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    i,j,k = 0,0,0
    
    while i < len(left) and j <len(right): # i와 j가 가리키는 값 비교 -> 작은 값을 k에 넣기
    	if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1
        
    if i == len(left): # 한쪽 리스트가 끝난 경우, 나머지 리스트를 넣어줌
    	while j <len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
    	while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
    return array
    
n = int(input())
array = []

for _ in range(n):
    array.append(int(input())
    
array = merge_sort(array)

for data in array:
	print(data)

 

 

2-2. 기본 정렬 라이브러리 이용

n = int(input())
array = []

for _ in range(n):
    array.append(int(input()))

array = sorted(array)

for data in array:
    print(data)

 

 

문제 출처 : https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2