코딩테스트 준비- 백준 2751번:병합정렬,리스트 정렬 예제(파이썬)

문제풀러가기

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

2751번: 수 정렬하기 2

---

---

풀이

두 방법 다 python3가아닌 pypy3로 풀어야 될 것.

(python3로 하면 시간초과가 뜹니다.)

1번 방법: sort 사용

2번 방법: merge sort(병합정렬) 사용

---

방법 1)

sort 리스트 정렬

N = int(input())
arr = []

for i in range(N):
  arr.append(int(input()))

arr.sort()
for i in arr:
  print(i)

---

방법 2)

병합 정렬 사용

(수정사항: 모르고 똑같은 이미지 두개를 올렸었네요 ㅠ_ㅠ 수정했습니다.)

병합정렬 예)

arr = [10, 12, 22, 3, 8, 1, 2, 56, 13]일때, 병합정렬을 통해

오름차순으로 리스트 정렬하는 법.

코드

def merge_sort(array):
  if len(array)<=1:
    return array
  mid = len(array)//2

  #left는 array리스트의 인덱스 0부터 mid전까지
  left = merge_sort(array[:mid]) 

  #right은 array리스트의 인덱스 mid부터 끝까지
  right = merge_sort(array[mid:])

  i, j, k = 0, 0, 0
  arr = []
  
  #둘중 하나조건에 부합하지 않을경우 while문 빠져나감 
  while i < len(left) and j < len(right): 
    if left[i] < right[j]:
      arr.append(left[i])
      i+=1
    else:
      arr.append(right[j])
      j+=1

#while문 빠져 나온 후, left혹은 right에 남은 요소들 arr에 넣어주기
  arr += left[i:] 
  arr += right[j:]
 
  return arr

N = int(input())
arr=[]

for _ in range(N):
  arr.append(int(input()))

arr = merge_sort(arr)

for i in arr:
  print(i)