[BOJ/PYTHON] 11582. 치킨 TOP N (정렬)

백준 문제 링크: https://www.acmicpc.net/problem/11582

문제 요약

치킨 집 정렬하고자 함

N/2명이 차례대로 2개의 치킨집을 선택해 정렬 → N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택하여 치킨집 정렬 → 계속해서 N/8명, N/16명이 정렬을 진행 → 마지막 사람이 두 개의 정렬된 그룹을 합병하여 작업을 완료.

현재 단계에서 k명의 회원이 정렬을 진행할 때 정렬을 마친 뒤 결과를 출력

핵심 아이디어

n, k 둘다 2의 거듭제곱이라 n을 k로 나눈 몫만큼 숫자를 자를 수 있다.

k명이 정렬하면 전체 치킨집 개수인 n을 k만큼 나눈 n // k 개씩 나눠서 정렬하게 된다. 그만큼 끊어서 각각 정렬하고 이어붙여 출력하면 된다.

풀이

# silver4-11582. 치킨 TOP N

import sys
input = sys.stdin.readline

n = int(input()) # 치킨집 개수 (2의 거듭제곱)
taste_nums = list(map(int, input().split())) # 치킨집 맛의 수치
k = int(input()) # 정렬 진행중인 회원의 수 (2의 거듭제곱)

# k명이 정렬하면 전체 치킨집 개수인 n // k 개씩 나눠서 정렬하게 됨.
# 그만큼 끊어서 각각 정렬하기
step = n // k
for i in range(step, n + 1, step):
    print(*sorted(taste_nums[i - step : i]), end=' ')

실행 시간

메모리 147496KB, 시간 1048ms (python3)