[python] 백준 2750번 수 정렬하기1 : 병합정렬(merge sort)

문제

2750번: 수 정렬하기

 

알고리즘

[JAVA] 백준 2751번 수 정렬하기2 : 병합 정렬( Merger Sort )

 

위 알고리즘을 사용하여 풀었으나, 파이썬의 장점을 살리지 못한 풀이가 되었다. 파이썬은 리스트를 생성하고 복사하는 과정이 자유롭다. 그래서 분할과 병합로 구성된 병할정렬 풀이 시, left 리스트와 right리스트를 분할생성하고 병합시 병합리스트를 만들어 반환하는 방식으로 풀어야 한다. 

코드

1) 내가 짠 코드 

import sys
sys.setrecursionlimit(10**6)

n = int(input())

input_arr = []
for i in range(n) :
  input_arr.append(int(input()))

#mersort시작
#left, right는 자료구조가 아닌 인덱스
def merge_sort(left,right) :
  if left < right :
    center = int((left+right)/2)
    #분할시작
    merge_sort(left,center)
    merge_sort(center+1,right)
  
    #정렬시작
    do_sort(left,right)

# 정렬, 임시배열 하나만 생성하고 index를 기억할 pointer 변수를 생성하여 정렬
def do_sort(left,right) :
  
  #임시배열생성
  buff = []
  center = int((left+right)/2) 

  #비교를 위한 포인터 변수 생성
  buff_pointer = 0 #임시배열포인터
  right_pointer = center + 1 #우측배열포인터
  arr_pointer = left # 전체배열포인터
  
  #left배열을 임시배열에 복사
  buff = input_arr[left : center+1] # 끝은 +1을 해주어야 center 이전까지 복사된다.

  #정렬 시작
  while buff_pointer < len(buff) and right_pointer <= right :
      leftvalue = buff[buff_pointer]
      rightvalue = input_arr[right_pointer]
      if leftvalue < rightvalue : 
        input_arr[arr_pointer] = leftvalue 
        buff_pointer += 1
      else : 
        input_arr[arr_pointer] = rightvalue
        right_pointer += 1
      arr_pointer += 1
    
  while buff_pointer < len(buff) :
    input_arr[arr_pointer] = buff[buff_pointer]
    arr_pointer += 1
    buff_pointer += 1

#병합정렬 호출
merge_sort(0,n-1)

#출력
for i in range(n) :
  print(input_arr[i])

 

 

 

2) 파이썬의 장점을 살린 코드 

import sys
sys.setrecursionlimit(10**6)

n = int(input())

input_arr = []
for i in range(n) :
  input_arr.append(int(input()))

# 병합정렬 시작, 리스트 중심으로 분할
def merge_sort(unsorted_arr) :
  if len(unsorted_arr) <= 1 : # 리스트 길이가 1 이하일때 리스트 반환
    return unsorted_arr  

  mid = len(unsorted_arr)//2 #중간값
  left = unsorted_arr[:mid] # left 리스트 생성
  right = unsorted_arr[mid:] # right 리스트 생성

  left_list= merge_sort(left) #left 리스트 분할 및 정렬
  right_list = merge_sort(right) #right 리스트 분할 및 정렬

  return merge(left_list,right_list) # left + right 정렬

def merge(left,right) : 
  i,j=0,0 
  sorted_arr = [] # 정렬된 리스트

  while i < len(left) and j < len(right) : #left, right 비교하여 정렬
    if left[i] < right[j] :
      sorted_arr.append(left[i])
      i += 1
    else :
      sorted_arr.append(right[j])
      j += 1

  if i < len(left) : sorted_arr += left[i:] # sorted_arr에 추가되지 않은 left의 값이 남은 경우 
  if j < len(right) : sorted_arr += right[j:] # sorted_arr에 추가되지 않은 right의 값이 남은 경우
    
  return sorted_arr #정렬된 리스트 반환

result = merge_sort(input_arr)

for i in range(n) :
  print(result[i])