백준 11582번 치킨 TOP N (Python)

문제

• 문제

인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많아 혼자 정렬을 하기에는 많은 시간이 걸려 C.T.P 회원들을 활용하기로 했다. 치킨집이 N개 있다고 가정을 하자. N개의 치킨의 수치를 무작위로 놓은 뒤 N/2명의 C.T.P 회원이 차례대로 2개의 치킨집을 선택해  정렬을 한다. 그 뒤 N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택 하여 치킨집을 정렬을 한다. 계속해서 N/8명, N/16명이 정렬을 진행하다가 마지막 사람이 두 개의 정렬된 그룹을 합병하여 작업을 완료한다.

예를 들어 8개의 치킨집의 점수가 (1, 5, 2, 4, 2, 9, 7, 3)과 같을 때, 첫 번째로 4명의 회원이(1, 5), (2, 4), (2, 9), (7, 3)을 각각 정렬하게 되면 (1, 5), (2, 4), (2, 9), (3, 7)이 되고, 두 번째로 2명의 회원이 ((1, 5), (2, 4))와 ((2, 9), (3, 7))을 정렬하면 (1, 2, 4, 5), (2, 3, 7, 9)가 되고, 최종적으로 1명의 회원이 ((1, 2, 4, 5), (2, 3, 7, 9))을 정렬하여 (1, 2, 2, 3, 4, 5, 7, 9)을 만들게 된다.

작업을 진행하던 중 문득 민호는 작업의 중간단계가 궁금해졌다. 현재 단계에서 k명의 회원이 정렬을 진행할 때 정렬을 마친 뒤 결과를 출력해라.

입력
첫 번째 줄에 치킨집의 개수 N(4 ≤ N ≤ 220)이 주어진다. N은 항상 2의 거듭제곱 꼴이다.

두 번째 줄에는 N개의 치킨집의 맛의 수치들이 빈칸을 구분으로 주어지며 이 값은 10억보다 작거나 같은 자연수 또는 0이다.

세 번째 줄에는 현재 정렬을 진행중인 회원들의 수 k(1 ≤ k < N)가 주어진다. k 또한 2의 거듭제곱 꼴이다.

출력
현재 단계에서 k명이 정렬을 진행한다고 할 때, 현재 단계가 완료한 상태를 출력하라.

• 입력과 출력

입력
첫 번째 줄에 치킨집의 개수 N(4 ≤ N ≤ 2^20)이 주어진다. N은 항상 2의 거듭제곱 꼴이다.

두 번째 줄에는 N개의 치킨집의 맛의 수치들이 빈칸을 구분으로 주어지며 이 값은 10억보다 작거나 같은 자연수 또는 0이다.

세 번째 줄에는 현재 정렬을 진행중인 회원들의 수 k(1 ≤ k < N)가 주어진다. k 또한 2의 거듭제곱 꼴이다.

출력
현재 단계에서 k명이 정렬을 진행한다고 할 때, 현재 단계가 완료한 상태를 출력하라.

• 예제 입력

8
1 5 2 4 2 9 7 3
2

• 예제 출력

1 2 4 5 2 3 7 9

문제 해결 접근

• 문제를 읽고 처음에 떠오른 아이디어는 merge sort를 진행하는 와중 일정한 중간 단계를 출력하는 문제.
• merge sort는 재귀적으로 들어가는데, 완료 조건을 어떻게 넣어줘야하지? 에 초점을 맞춰서 소스 코드를 작성
• merge sort 파이썬 코드는 정리되어 있는 블로그 글 참고

정답 코드

import sys

## 입력
N = int(sys.stdin.readline())
array = [int(i) for i in sys.stdin.readline().strip().split()]
K = int(sys.stdin.readline())


## merge sort
def merge_sort(arr, low, high, n, k):
  if (low >= high):
    return  # base case

  mid = (low + high) // 2
  merge_sort(arr, low, mid, n, k)  ## 앞부분 (재귀적으로 들어옴)
  merge_sort(arr, mid + 1, high, n, k)  ## 뒷부분 (재귀적으로 들어옴)

  if high - low < n // k:
    sorted_array = merge(arr, low, high)  ## 계속 merge 할 떄까지 진행
  else:
    sorted_array = arr  ## 아닌 경우 더이상 진행하지 않기

  # 재귀적으로 들어가는 부분을 확인하기 위해서 찍어보기
  # print("***")
  # print(f"input : {arr, low, high, n, k}")
  # print(sorted_array)

  return sorted_array


def merge(arr, low, high):
  temp = []
  mid = (low + high) // 2
  i, j = low, mid + 1

  ## 앞부분과 뒷부분에서 같은 위치에 있는 요소를 비교하여 넣어주기
  while i <= mid and j <= high:
    if arr[i] <= arr[j]:
      temp.append(arr[i])
      i += 1
    else:
      temp.append(arr[j])
      j += 1

  ## 남은 부분이 있다면 그 부분을 뒤에 넣어주기
  while i <= mid:
    temp.append(arr[i])
    i += 1

  while j <= high:
    temp.append(arr[j])
    j += 1

  ## temp에서 정렬된 것을 array에 넣어주기
  for k in range(low, high + 1):
    arr[k] = temp[k - low]

  return arr

## 출력 
answers = merge_sort(array, 0, N - 1, N, K)
for i in answers:
  print(i, end=' ')

정답 코드 해설

1) 입력

import sys

## 입력
N = int(sys.stdin.readline())
array = [int(i) for i in sys.stdin.readline().strip().split()]
K = int(sys.stdin.readline())

• 입력 받는 부분 : 요즘에 Input보다 sys로 받는 것으로 바꿔보고 있다.
• input == sys.stdin.readline 이라고 기억하면 편하다.

2) Merge sort

## merge sort
def merge_sort(arr, low, high, n, k):
  if (low >= high):
    return  # base case

  mid = (low + high) // 2
  merge_sort(arr, low, mid, n, k)  ## 앞부분 (재귀적으로 들어옴)
  merge_sort(arr, mid + 1, high, n, k)  ## 뒷부분 (재귀적으로 들어옴)

  if high - low < n // k:
    sorted_array = merge(arr, low, high)  ## 계속 merge 할 떄까지 진행
  else:
    sorted_array = arr  ## 아닌 경우 더이상 진행하지 않기

  # 재귀적으로 들어가는 부분을 확인하기 위해서 찍어보기
  # print("***")
  # print(f"input : {arr, low, high, n, k}")
  # print(sorted_array)

  return sorted_array

• merge sort : 기본적으로 merge sort는 divide conquer, merge_sort가 계속 나눠주고, merge는 합친다.
• 기본적인 코드에서 merge는 바꾼 것이 없고, merge_sort가 재귀적으로 들어갈 떄 종료조건을 설정해주는 것에 초점
• high- low < n//k 일 때는 merge 함수를 호출해서 sort를 진행하고, 그렇지 않을 떄에는 정렬하지 않고 함수를 반환하게 만들기
  
• 주석처리 해놓은 Print 부분처럼 재귀적으로 들어가는 부분을 확인해보면, 아래 사진과 같은데, 그걸 보면 완료 조건을 어떻게 주면 좋을지 판단하기 쉬웠다. 재귀함수에 특히 약한데, 앞으로도 문제 이해가 필요하면 이렇게 찍어보면 좋을 것 같다.

3) 출력

## 출력 
answers = merge_sort(array, 0, N - 1, N, K)
for i in answers:
  print(i, end=' ')

• 출력을 굳이 적은 이유는 오늘 제출하다가, 출력 형식에 안 맞춰서 틀렸습니다가 계속 나오길래 거기서 시간 낭비 했기 때문...^^ 출력도 제대로 잘 확인하자!