[프로그래머스] Lv4 - 선입 선출 스케줄링

프로그래머스 레벨4 - 선입 선출 스케줄링

간만에 엄청 고생해서 푼 문제였다.

백준같은 사이트는 시간 제한이 1초, 2초 이런식으로 걸려있지만.. 프로그래머스는 그렇지 않았기에 매우 신경써서 풀이를 찾아야 했다. 추측해보기로는 ‘모범답안 소요시간의 2~3배까지 허용’ 이런식으로 채점되는건 아닐까 싶었음.

개인적으로 이 문제에서 생각할 수 있는 풀이는 3개 정도였다.

1) 제일 무식하게 풀기

작업을 하나씩 처리하면서 일일히 확인해보는 시뮬레이션 코드 (for문 사용해서..)
예를 들어 현재 시간이 n이고 코어 번호를 m이라고 한다면, n을 1씩 증가시켜가면서 모든 코어를 일일히 확인해본다. n이 m으로 나누어 떨어지면 남은 작업 개수를 하나씩 깎아나가는 식.

2) 비교적 최적화된 풀이

Priority Queue 사용해서 작업 순서를 확인
해당 작업을 수행하는 코어 번호 및 작업이 종료되는 시간을 저장하는 Work 클래스를 만들고, Work 객체를 담을 수 있는 PQ를 생성 (종료시간을 서로 비교하도록 처리하고 종료시간이 같은 경우는 코어 번호를 비교)

3) 모범답안이랑 거의 비슷하게 시간 걸리는 풀이

1번이면 몰라도, 2번 정도면 문제에서 요구하는 제한 사항을 꽉 채워서 돌려봐도 30ms 수준에서 답을 얻을 수 있었다.

그런데도 통과하지 못했고 며칠을 삽질했다. (효율성 케이스가 6개 있었는데 그 중 딱 1개만 통과할 수 있었다)

결국은 지인 분이 “파라메트릭 서치 써보는게 어때요?” 라고 하셔서 코드를 다 지우고 새로 짰다.

가까스로 모든 케이스를 통과할 수 있었고, ‘이정도면 됐지’라고 생각이 들 때는 충분히 더 좋은 케이스가 없을지 의심해봐야된다는 교훈을 얻은 시간이었다.

얼핏 보면 파라메트릭 서치가 안먹힐 줄 알았으나, 다음과 같은 방식으로 접근하니 가능했다.

마지막 작업이 큐에 들어가는 시간을 찾아내는 이분탐색을 한다. 여기서 (cores 배열에서 가장 작은 값 * 작업 개수 / 코어 개수) 값을 min으로 잡고, 가장 작은 값 * 작업 개수를 max로 잡고 mid값이 조건에 맞는지 탐색한다.
제일 처음 시간인 0초에는 모든 코어에 순차적으로 작업이 한개씩 삽입되므로, 각 코어가 작업을 마치고 새 작업을 삽입하는 시간은 반드시 (현재 시간 % 코어 작업 수행 시간 == 0)을 만족한다. 그러므로 mid / cores[i]를 계산하면 ‘mid 시간 도달 직전까지 이 코어는 몇 개의 작업을 수행했는지’ 알아낼 수 있다.
mid값을 정했으면 각 코어를 순회하면서 ‘mid 시간 도달 직전까지 이 코어는 몇 개의 작업을 수행했는지’ count를 계산해서 누적해준다. ‘mid 시간에서 작업 삽입 가능한 코어의 개수’와 count를 더했을 때 작업 개수를 충족할 수 있는지 확인. 조건에 맞지 않으면 min이나 max를 조절해가면서 이분 탐색 계속 진행
조건에 맞는 mid 시간을 얻어낸 경우 cores[0]부터 쭉 순회해서, (mid % cores[i] == 0) 만족하면 count를 1씩 증가해주고 (count == n)이 되는 코어 번호를 찾아서 리턴해주면 된다.

파라메트릭 서치에 대해서는 PS 잘하시는 분들 블로그를 찾아보면 설명이 잘 되어있고 따라서 여기서는 자세히 쓰지 않겠다. 아래 코드는 Java 기준으로 3~6ms 정도의 시간이 걸린다.