[CodingTest] 백준 10814번 나이순 정렬 : 단어정렬 - 퀵, 병합, 힙정렬

 

문제) 

1181번: 단어 정렬

 

풀이 ) 

퀵정렬, 병합정렬, 힙정렬로 풀었다. 버블정렬은 시간초과가 발생한다. 파이썬은 리스트에 중복된 값을 제거할 때, 조건문에 not in 연산자를 사용하면 된다. 나는 이를 힙정렬 풀이 때 알게 되어 힙정렬에서 not in 연산자를 이용하여 풀었다. 

 

- 퀵정렬 풀이

# 입력
n = int(input())

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

# 퀵소트 함수
def quicksort(unsorted) :
  # 리스트에 아이템이 1개 이하인 경우 ( 기저조건 )
  if len(unsorted) <=1 : return unsorted

  pivot = unsorted[0] # 기준값
  left = [] # 왼쪽 리스트 
  right = [] # 우측 리스트

  # 기준값보다 작으면 left에 크면 right에 append
  for i in range(1,len(unsorted)) :
    if len(pivot) > len(unsorted[i]) : left.append(unsorted[i])
    elif len(pivot) < len(unsorted[i]) : right.append(unsorted[i])
    else : # 문자열 길이가 같은 경우
      if pivot > unsorted[i] : left.append(unsorted[i])
      elif pivot < unsorted[i] : right.append(unsorted[i])
      # 문자열이 같은 경우, left와 right 에 넣어주지 않아 자동으로 중복제거
      
  return quicksort(left) + [pivot] + quicksort(right)

#출력
result = quicksort(input_list)
for i in range(len(result)) :
  print(result[i])

 

 

- 병합정렬 풀이 

#입력
n = int(input())
input_list = []
for i in range(n) :
  input_list.append(input())

#병합정렬
def merge_sort(unsorted) :
  #기저조건
  if len(unsorted) <= 1 : return unsorted

  #분할 수행
  mid = len(unsorted)//2 #분할 위치
  left = unsorted[:mid] # 분할된 왼쪽
  right = unsorted[mid:] # 분할된 오른쪽

  #정렬 수행
  left_sorted = merge_sort(left) # 좌측병합정렬
  right_sorted = merge_sort(right) # 우측병합정렬

  return merge(left_sorted,right_sorted) # 병합수행

#병합수행함수
def merge(left, right) :

  leftP, rightP = 0,0
  sorted = []

  while leftP < len(left) and rightP < len(right) :

    if len(left[leftP]) < len(right[rightP]) : 
      sorted.append(left[leftP])
      leftP += 1

    elif len(right[rightP]) < len(left[leftP]) :
      sorted.append(right[rightP])
      rightP+= 1
    #문자열 길이가 같은경우
    else : 
      if left[leftP] < right[rightP] : 
        sorted.append(left[leftP])
        leftP += 1
      elif right[rightP] < left[leftP] :
        sorted.append(right[rightP])
        rightP+= 1
      else : #문자열이 같은 경우 ( 중복 제거 )
        sorted.append(left[leftP])
        leftP += 1
        rightP += 1 # 같이 넘어가주어야 중복이 방지된다. 

  # 남은 값이 있는 경우
  if leftP < len(left) : sorted += left[leftP:]
  if rightP < len(right) : sorted += right[rightP:]

  return sorted

#출력
result = merge_sort(input_list)
for i in range(len(result)) :
  print(result[i])

 

 

- 힙정렬 풀이 

#입력받기
n = int(input())

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

#문자열 비교함수
def is_smaller(value,target) :
  if len(value)<len(target) : return True
  elif len(value) > len(target) : return False
  else : 
    if value < target : return True
    elif value > target : return False
    else : return True

# 힙소트
def heap_sort(unsorted) :
  #힙트리생성
  last_child = len(unsorted)-1
  last_parent = (last_child-1)//2 

  # 가장 마지막 부모부터 루트까지 힙트리 생성하기
  for i in range(last_parent,-1,-1) :
    heapify(unsorted,i) 
    
  #힙정렬 
  sorted = []
  for i in range(len(unsorted)-1,-1,-1) : 
    unsorted[i], unsorted[0] = unsorted[0],unsorted[i] # 루크와 가장 마지막 값 스위칭
    value = unsorted.pop(i) # 마지막 위치값 pop하여 정렬리스트에 추가하기
    if value not in sorted : sorted.append(value) # not in으로 중복 확인하여 추가하기
    if i != 0 : heapify(unsorted,0) # i=0이면 더이상 unsorted에 정렬할 item이 없음

  return sorted

#힘트리 생성 함수
def heapify(unsorted,index) :
  pointer = index
  pivot = unsorted[pointer]

  while pointer <= ((len(unsorted)-1)-1)//2 : #가장 마지막 부모까지 반복
    #좌측, 우측 중 큰값을 가진 자식 고르기
    left_child = 2*pointer+1
    right_child = left_child+1
    child = ( right_child if right_child < len(unsorted) and is_smaller(unsorted[right_child],unsorted[left_child]) else left_child )

    #부모와 자식 값 비교하여 최솟값을 부모로 올리기 
    if is_smaller(pivot,unsorted[child]) : break #부모가 최솟값이므로 반복종료
    else : # 자식이 최솟값이므로 자식을 부모로 올리기
      unsorted[pointer] = unsorted[child]
      pointer = child # 부모였던 값은 자식으로 내려가기

  unsorted[pointer] = pivot  #현재 위치에 값을 저장하고 힙트리생성함수 종료

#출력
result = heap_sort(input_list)
for i in range(len(result)) :
  print(result[i])

 

 

 

---

 

번외) 버블정렬 풀이 [ 시간초과 발생 주의! ]

#입력받기
n = int(input())
unsorted = []
for i in range(n) :
  unsorted.append(input())

# 문자열 길이 비교 함수
def is_bigger(value1, value2) :
  if len(value1) > len(value2) : return True
  elif len(value1) < len(value2) : return False
  else :  #문자열 길이가 같은 경우
    if value1 > value2 : return True
    elif value1 < value2 : return False
  

for i in range(len(unsorted)) :
  for j in range(len(unsorted)-1,i,-1) :
    #두 문자열이 같은 경우
    if unsorted[j] == unsorted[j-1] : 
      unsorted.pop(j) #문자열 하나 제거
      continue # 같은 문자열인 j-1에서 비교를 하기 위해, continue로 진행
    # 문자열 비교 후 swap
    if not is_bigger(unsorted[j],unsorted[j-1]) :
      unsorted[j], unsorted[j-1] = unsorted[j-1],unsorted[j] #swap

for i in range(len(unsorted)) :
   print(unsorted[i])