문제분석
목표: 작업들을 순서대로 넣으며 작업하다가 맨 마지막에 작업을 맡게되는 코어를 구하세요.
문제를 읽어보면 최적의 시간을 구하는 문제가 아니다.
0초에 코어가 비어있다면 무조건 작업을 넣어놓기때문이다.
[1, 1, 100] 의 코어가 있고 4개의 작업이있다면 100의코어에 그냥 집어넣는꼴이다.
이를 감안하고 접근을해야한다.
문제접근 1: 문제설명서대로 풀기
0초에 모든 작업을 넣고
1초에 다시 작업이 가능한지 확인하고
2초에 다시 작업이 가능한지 확인하고
. . .
마지막 작업이 들어가면 그 코어를 반환하는 로직이다.
이렇게 구현하면 매 초마다 모든 코어를 돌려봐야하므로 O(n)만큼 든다.
-> 정확도는 잘 나오지만 효율성 에러가 뜬다.
문제 접근 2: 효율성 해결
아마 효율성 에러가 뜨는 원인은 0초부터 매초 마다 O(n)의 작업을 하기때문일것이다.
O(n)의 작업을 최소한 줄이기위해선, 마지막 작업을 수행하는 시간(time)을 구해야한다.
마지막 작업의 시간을 이분 탐색으로 구한다.
최소값은 0 . 최대값은 코어의갯수 * (코어의 최대시간)
mid의 시간에 수행한 모든 작업의 갯수가 N보다 작으면 UP 크면 Down을 작업한다.
이 작업을 시행하면 T*O(N)이 log(T)*O(N)으로 줄어든다.
문제풀이
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | import java.util.*; class Solution { public int solution(int n, int[] cores) { int answer = 0; int min = 0; // 시간의 최소값 int max = 10000*n; // 시간의 최대값 int time = 0; int m = 0; while (true) { int mid = (min+max)/2; int count = calculate(mid, cores); if(min>max){ break; } if (count >= n) { // 해당시간까지 처리한 작업량보다 n이 크면 time과 m갱신 max = mid-1; time = mid; m = count; }else{ min = mid+1; } } m-=n; // 처리한 작업량과 n의 차이 갱신 for(int i = cores.length-1; i>=0; i--){ if (time % cores[i] == 0) { if (m == 0) { answer = i+1; break; } m--; } } return answer; } static int calculate(int time, int[] cores){ if (time == 0) { // 시간이 0일 때, 처리할 수 있는 작업량은 코어의 개수 return cores.length; } int count = cores.length; // 시간이 0일 때, 처리한 작업량 for(int i = 0; i<cores.length; i++){ // time까지 코어가 처리할 수 있는 작업량 합산 count += (time/cores[i]); } return count; } } | cs |