[문제 출처 : Codechef] 기나긴 연회가 끝나고, 이제 장소를 청소하고 정리하는 일만 남았습니다.
주방에는 쉐프와 보조 두 명만 남았습니다.
총 치워야 할 n개의 일 중에 m개는 이미 나머지 종업원들이 마쳤습니다.
쉐프와 보조는 다음과 같은 규칙으로 나머지 하지 않은 일들을 분담하려고 합니다.쉐프가 가장 빠른 index의 일을 맡습니다. 보조가 그 다음으로 빠른 index의 일을 맡습니다. 이런식으로 계속 반복해서 남은 일들을 할당합니다.
이 경우에 결국 쉐프와 보조가 받게 되는 일들은 각각 어떤 것들일까요?
문제에서는 숫자 n과, 끝난 일들의 index들이 들어있는 list가 주어지게 됩니다. 이 때 어떻게 하면 효과적으로 쉐프와 보조에게 일을 할당해 줄 수 있을까요?
먼저 가장 핵심적인 부분은 이미 완료된 일들의 index들을 오름차순으로 정렬하는 일입니다. 그렇게 되면 각 index들의 사이사이를 하나씩 돌아가면서 할당해 주면 되겠죠? 그리고 또 하나의 팁은, 처음엔 0을 넣어주어서 작업을 1부터 고려하게끔 하고, 마지막엔 n+1을 넣어주어서 n까지 고려하게끔 해주는 것입니다.
이제 코드로 작성해 보고 결과를 확인해 보겠습니다.
def assignJobs(n, completed):
completed.sort() #일단 오름차순으로 정렬을 해 줍니다.
#맨 처음에 0을 넣고, 마지막에 n+1을 넣어줌으로써 모든 비어있는 작업들에 대해 반복할 수 있게 됩니다.
completed.insert(0, 0)
completed.append(n+1)
turn = True #True가 쉐프입니다.
chefs = []
assists = []
#구간별로 빈 작업들을 할당해 줍니다.
for i in range(len(completed)-1):
for j in range(completed[i]+1, completed[i+1]):
if turn:
chefs.append(j)
else:
assists.append(j)
turn = not turn
print "쉐프에게 할당된 작업 : ", chefs
print "보조에게 할당된 작업 : ", assists
>>> assignJobs(6, [2,4,1])
쉐프에게 할당된 작업 : [3, 6]
보조에게 할당된 작업 : [5]
>>> assignJobs(3, [3,2])
쉐프에게 할당된 작업 : [1]
보조에게 할당된 작업 : []
>>> assignJobs(8, [3,8])
쉐프에게 할당된 작업 : [1, 4, 6]
보조에게 할당된 작업 : [2, 5, 7]