[BOJ/백준] 11582번 파이썬 - 치킨 TOP N

문제

백준 11582 치킨 TOP N

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

11582번: 치킨 TOP N

 

문제풀이

merge sort 의 중간 과정을 출력하는 문제 ; k명이 정렬하는 단계가 완료된 상태 출력
merge 함수를 만들어서 merge sort 진행하기
check 함수를 만들어서 k명 미만이 정렬하면 정렬 중지시키기

코드

import sys
input=sys.stdin.readline

def check(s,e):
    if((e-s)>(n/k)):  ##정렬 정지 조건
        return
    mid=int((s+e)/2);
    idx1=s; idx2=mid+1; idx3=0;
    
    while(idx1<=mid and idx2<=e):
        if(num[idx1]<=num[idx2]):
            tmp[idx3]=num[idx1]
            idx3+=1; idx1+=1
        else:
            tmp[idx3]=num[idx2]
            idx3+=1; idx2+=1
    while(idx1<=mid):
        tmp[idx3]=num[idx1]
        idx3+=1; idx1+=1
    while(idx2<=e):
        tmp[idx3]=num[idx2]
        idx3+=1; idx2+=1
    for i in range(s,e+1):
        num[i]=tmp[i-s]
        
def merge(s,e):
    if s==e:
        return
    mid=int((s+e)/2)
    merge(s,mid)
    merge(mid+1,e)
    check(s,e)
    

n=int(input())
num=list(map(int,input().split()))
tmp=[0]*n
k=int(input())
merge(0,n-1)
print(*num)

여기서

• if(e-s>n/k): return
• e-s = 정렬중인 리스트의 크기 , (n/k) = k명 당 정렬해야하는 배열의 크기

을 의미!

 

어려웠던 점

코드 짜는거 자체는 크게 어려운 게 아니었는데 정렬 정지 조건을 생각하는 것이 좀 어려웠다

그 단계가 완료된 이후의 정렬 값을 출력하는 것이라서 더 헷갈렸움 ㅜㅜ