[Java] 프로그래머스 level3 선입 선출 스케줄링 (시간초과...)

https://school.programmers.co.kr/learn/courses/30/lessons/12920

프로그래머스

 

코딩테스트 연습 > 연습문제 > 선입 선출 스케줄링 

 

문제 설명

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.
이 CPU는 다음과 같은 특징이 있습니다.
CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.
처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.

 

제한 사항

코어의 수는 10,000 이하 2이상 입니다.
코어당 작업을 처리하는 시간은 10,000이하 입니다.
처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.

 

문제 접근1

우선순위 큐를 통한 접근

작업이 끝나는 시간이 다르면 작업이 끝나는 시간이 빠른 순서대로 

작업이 끝나는 시간이 같으면 core 번호가 빠른 순서대로 정렬하였다. 

시간 초과 코드1 ( 정확성 : 70.0  효율성 : 0.0 ) 

import java.util.*;

class Solution {
    public int solution(int n, int[] cores) {
        int answer = 0;
        
        // CPU [0] = core 번호 [1] = 처리하는 시간 [2] = 작업이 끝나는 시간 
        PriorityQueue<int[]> CPU = new PriorityQueue<>(
        (o1, o2) -> {
            if(o1[2]!=o2[2]) return o1[2] - o2[2];
            return o1[0] - o2[0];
        });
        
        int size = cores.length;
        for(int i = 0; i < size; i++){
            CPU.add(new int []{i+1,cores[i],0});
        }
        
        int cnt = 0;
        int time = 1;
        while(true){
            while(CPU.peek()[2] <= time){
                cnt++;
                int[] temp = CPU.poll();
                if(cnt == n){
                    return temp[0];
                }
                temp[2] = time + temp[1];
                CPU.add(temp);
            }
            time++;
        }
    }
}

 

 

문제 접근2

배열을 사용해서 풀었다.

1번 core ~ 마지막 core 까지 끝나는 작업 시간이 현재 시간보다 작거나 같으면

작업을 하게 만들었다.

통과를 예상 했지만..?

시간 초과 코드 2( 정확성 : 70.0  효율성 : 0.0 ) 

import java.util.*;
class Solution {
    public int solution(int n, int[] cores) {
        int answer = 0;
        
        int size = cores.length;
        int [] cpu = new int[size];
        
        int cnt  = 0;
        int time = 1;
        
        while(true){
            for(int i = 0; i < size; i++){
                if(cpu[i] <= time){
                    cnt++;
                    if(cnt == n) return i + 1;
                    cpu[i] = time + cores[i];
                }
            }
            time++;
        }
    }
}

 

 

문제 접근3

ing...

아마 이분 탐색으로 풀어야 시간 초과가 발생하지 않을듯하다. 

조만간 풀어보겠다!