[문제 출처 : 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]