23.02.24 파이썬 코딩 퀴즈#170 선입 선출 스케줄링 (프로그래머스 스쿨)

이번 문제는 선입 선출 스케줄링 문제이다.

문제로 주어지는 n 개의 작업을 CPU 에 나누어 처리하게 되는데, 이때 마지막 작업을 처리한느 코어의 번호를 return 해야 한다. 코어는 여러개가 주어지고, 앞에서 부터 하나씩 작업을 할당하게 된다. 그리고 작업이 끝난 코어에는 바로 다음 작업이 배정된다.

입출력 예 에서 할 수 있듯이 cores 라는 변수에 3개의 cpu가 전달 되었으며, 각 cpu 별로 작업 처리 속도가 정해진다.

1은 1시간에 1개의 작업을 2는 2시간에 1개의 작업을 완료함을 나타낸다.

처음 에는 각 core에 하나의 작업이 배정되며, 이때 3개의 작업이 남게 된다.

1시간 뒤에 1번 의 작업이 끝나면 다시 1개의 작업을 배정한다. 그리고 2개의 작업이 남는다.

다시 1시간 뒤에 1번과 2번의 작업이 끝나고, 순서대로 1번, 2번으로 작업이 배치된다. 동시에 배치되는 모습이지만 실제로는 1번 -> 2번 순서로 작업이 배치되고, 남은 작업은 없기 때문에 반환해야 할 값은 2가 된다.

한가지 주의할 사항은 마지막 작업이 배정된 cores의 번호를 반환해야 한다는 점이다.

 

예를 들어 작업물 n이 10개이고, cores가 12개 라면, 당연히 10번째 cores에서 작업이 끝나므로 n 을 그대로 반환해주면 된다.

첫번째 작성한 코드이다. 시간 경과에 따라 working 에 저장된 값들을 1씩 감소 시켜주고, 0이 되었을 때, 다시 값을 회복시켜주는 방식으로 작성하였다.

역시나 효율성 검사에서 문제가 발생하였다.

레벨3 문제부터는 먼가 효율성을 요구하는게 더 빡빡해졌다.

그렇게 작성한 두번째 코드

먼저 maxtime 을 설정해 준다. maxtime 은 cores 중 가장 작업 속도가 느린 (값이 큰) 단일 요소로 n을 작업하는데 걸리는 시간이다.

그리고 이분탐색을 통해 해당 작업을 완료하는데 필요한 최소한의 시간을 계산해 주면 된다.

참고로 목표시간(mid)을 cores 의 각 요소로 나눈 몫은 해당 시간에 해당 코어로 작업 가능한 수량이 된다.

예를 들어 작업 시간이 10시간 이고 목표 시간이 40시간 이라면, 해당 코어가 작업 가능한 수량은 4 이다.

 

만약 mid 시간만큼 작업했을때 목표 n 보다 작업 수량 can_do 가 더 많다면, maxtime 을 mid로 변경한 뒤 해당 while문을 돌게 된다. 부족한 경우라면 시작시간(start)를 +1 해서 다시 mid 를 계산해 주게 된다.

 

이렇게 최종적으로 만들어진 maxtime 을 이용하여, 작업물을 진행할텐데

먼저 maxtime-1 만큼 작업하여 n 값에서 작업 한 수량만큼 제거한다.

그리고 다시 maxtime을 돌게 되는데 이때에는 몫이 아닌 나머지를 이용한다.

즉 나머지가 0 이라면 해당 시간에 한번 더 작업이 가능하다는 의미이고, 아니라면 그 시간에 작업이 불가능 하다는 의미이다. 

 

앞서 while문에서 can_do >= n 으로 maxtime 을 구해왔기 때문에 maxtime 번째 작업에서 반드시 해당 작업이 끝나게 된다.