[프로그래머스] 선입 선출 스케줄링 풀이 과정 기록 (Python,Java)_자바풀이추가예정

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

프로그래머스

 

 

간단해보여서 덤볐다가 애먹은 문제...

 

처음엔 과정을 이해하기 위해 일단 브루투포스로 과정을 생각을 해봤다.

time을 1초씩 증가시키며 상태를 처리한다.

 

🔍브루투포스 (시간초과)

def solution(n, cores):    
    cpu = {}
    for core in cores:
        cpu[core] = 0
    time = last = task = 0
    
    while task < n: # 50,000
        for key, val in cpu.items(): # 10,000
            if key == val:
                task+=1
                cpu[key] = 0
                last = key
            else:
                cpu[key] += 1
    
    return last

예상했듯 시간초과.
CPU가 10,000개일 수 있다.그리고 n도 50,000까지 가능.(주석을 참고하자)
최악의 경우, 모든 코어가 10,000초 걸리는 경우는 약 O(n * m) 복잡도 → 시간초과이다!

 

하지만!!! 난 더이상 속지않지 움하하...

 

그럼 결국 시간초과를 줄여야하는데...이런케이스에서

가장많이 쓰는게 이분탐색아니겠는가?!!? 

 

근데 여기서 어떤 코어에서 마지막작업이 처리되는지 구하는부분에서 막혀서 고수분들의 풀이를 참고했다^^데헷

해결 전략: 이분 탐색 (Binary Search)

이 문제는 "마지막 작업이 몇 초에 어떤 코어에서 할당되는지"를 찾는 것이므로, 시간을 기준으로 이분 탐색할 수 있다.

✨ 아이디어

1. mid 초까지 몇 개의 작업이 처리되는지를 계산
2. 이 값이 n보다 작으면 더 나중 시간 필요 (start = mid + 1)
3. 이 값이 n 이상이면 더 이른 시간에도 가능 (end = mid)
4. 그렇게 최적의 시간을 찾은 뒤, 그 시간에 어떤 코어에서 마지막 작업(n번째)이 처리되는지 순차적으로 확인

 

여기서 내가 헷갈렸던 건 4번 단계였다.

n번째 작업이 할당된 시간 t(예: 2초)를 기준으로 “마지막 작업이 어떤 코어에서 시작됐는지” 확인하려면,

바로 직전 시점(t–1초)까지 얼마나 많은 작업이 할당(start)됐는지를 먼저 알아야 하고,

그 값을 기준으로 t초에 새로 할당되는 코어들을 순서대로 살펴봐야 한다.

즉,
“t초에 할당되는 작업들 중 n번째가 어느 코어인지”를 찾기 위해
t–1초까지 누적된 할당 수를 구한 뒤,1
t초에 비어 있는 코어들에 하나씩 할당하면서 n번째가 되는 순간을 체크하는 방식이다!!

 

교훈: 이런문제풀때 간단하다고 뇌로 풀려하지말고 그림으로 그려서 따라가는게 중요한듯하다.

 

파이썬풀이

def solution(n, cores):
    if n <= len(cores):
        return n

    low_time = 0
    high_time = max(cores) * n

    while low_time < high_time:
        mid = (low_time + high_time) // 2
        allocated = sum(mid // c for c in cores) + len(cores)
        if allocated >= n:
            high_time = mid
        else:
            low_time = mid + 1

    completed = sum((low_time - 1) // c for c in cores) + len(cores)
    for i, c in enumerate(cores):
        if low_time % c == 0:
            completed += 1
            if completed == n:
                return i + 1
    return -1