[level 3] 선입 선출 스케줄링 - 12920

문제 링크

성능 요약

메모리: 54.3 MB, 시간: 8.18 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 70.0
효율성: 30.0
합계: 100.0 / 100.0

제출 일자

2025년 01월 18일 20:36:40

문제 설명

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.

이 CPU는 다음과 같은 특징이 있습니다.

• CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
• 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
• 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.

처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.

제한 사항

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

---

입출력 예

n	cores	result
6	[1,2,3]	2

입출력 예 설명

입출력 예 #1
처음 3개의 작업은 각각 1,2,3번에 들어가고, 1시간 뒤 1번 코어에 4번째 작업,다시 1시간 뒤 1,2번 코어에 5,6번째 작업이 들어가므로 2를 반환해주면 됩니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

문제 풀이

10000 x 10000이라 생각했지만 아니었다. 시간복잡도 계산을 먼저 깊게 해보고 구현해야겠다.

코드

1. 시간초과 코드 (최대 10000x10000이라 바로 써본 코드) -> 정확도는 다 맞았지만 효율성 (시간복잡도) 가 틀림.

class Solution {
    static boolean[][] work;
    static int r, c;
    public int solution(int n, int[] cores) {
        
        if (n <= cores.length) return n;
        
        int res=0;
        work = new boolean[cores.length + 1][10001];
        
        r = 1;
        c = 1;
        
        while(n>0 && isValid(r, c)){
            
            if(!work[r][c] && c + cores[r-1] - 1 <= 10000) {
                checkWork(cores);
                n--;
            
                if(n==0){
                    res = r;
                    break;
                }
            }
            convertCoord();
        }
        
        return res;
    }
    
    private void checkWork(int[] cores){
        for(int j=c; j<c+cores[r-1]; j++){
            work[r][j] = true;
        }
    }
    
    private boolean isValid(int r, int c){
        return r >= 1 && r <= work.length-1 && c >= 1 && c <= 10000;
    }
    
    private void convertCoord(){
        if(r == work.length-1) {
            if(isValid(1, c+1)){
                r=1;
                c++;
            }
        }
        else {
            if(isValid(r+1, c)) r++;
        }
    }
}

2. 시간초과코드 : 메모리때문일까싶어 다르게 나머지로 구현해본 코드

class Solution {
    public int solution(int n, int[] cores) {
        int res = 0;
        int time = 0;
        while(n>0){
            for(int i=0; i<cores.length; i++){
                if(time%cores[i] == 0){
                    n--; 
                    if(n==0) {
                        res = i+1;
                        break;
                    }
                }
            }
            time++;
        }
        return res;
    }
}

정답 코드 O(NlogN으로 시간복잡도 줄였음)

class Solution {
    public int solution(int n, int[] cores) {
        if(n <= cores.length) return n;
        
        n -= cores.length;
        
        int left = 1, right =  250000000;
        
        int res = 0;
        while(left <= right){
            int mid = left + (right - left)/2;
            
            long cnt = 0;
            for(int i=0; i<cores.length; i++){
                cnt += (long) mid / cores[i];
            }
            
            if(cnt >= n){
                res = mid;
                right = mid-1;
            }
            else{
                left = mid + 1;
            }
        }
        
        // 일단 res시간까진 작업이 완료된다는걸 찾음
        
        long work = 0;
        for(int i=0; i<cores.length; i++){
            work += (long) (res-1) / cores[i];
        }
        
        int ans = cores.length;
        
        for(int i=0; i<cores.length; i++){
            if(res % cores[i] == 0) {
                work++;
                if(work == n) {
                    ans = i+1;
                    break;
                }
            }
        }
        return ans;
    }
}