[프로그래머스] 코딩테스트 연습 - 선입 선출 스케줄링(Python)

문제 설명

문제

처리해야 할 동일한 작업이 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/courses/30/lessons/12920

프로그래머스

이전에는 level4 였는데, 지금은 level3 문제로 변경된 문제입니다. 문제 길이가 짧을 수록 효율높은 코드를 내야지만 통과하는 경우가 있는데, 이 문제도 그러했습니다.

직관적으로 풀고 제출하면, 분명 시간초과가 나는 코드로 효율성 이슈를 통과하지 못할 수 있습니다. 저는 이 문제는 풀 때, 결국 구글링의 도움을 받았습니다. 찾다보니, 이진탐색과 관련한 문제였습니다. 오랜만에 이진탐색 유형을 보니 반갑기도 했는데요, 코테에도 종종 등장할 수 있는 유형이니 공부할 수 있는 좋은 기회였습니다.

 

그럼, 먼저 문제를 이해해보도록 할게요.

# 1

처리해야 할 작업의 개수(n)가 CPU에 속해 있는 core의 개수보다 작거나 같으면, 그냥 답은 n이라는 것을 알 수 있습니다. 처음에 혼동할 수 있는데, 우리가 구해야하는 답은 마지막 작업을 처리하는 코어의 번호이므로,

 

우선, 시작은 전체 CPU에 있는 모든 코어에게 작업을 할당하는 것입니다. 그럼, 당연히 CPU에 있는 코어의 개수보다 작업량이 크지 않다면, 마지막 작업을 처리하는 CPU에 있는 코어의 번호는 n과 같다는 것을 알 수 있습니다.

다시 말해, 코어가 몇개 있는지를 나타내는 len(cores) 범위 안에 n 이 있다면, 마지막 작업을 처리하는 코어번호도 n이 되는 셈이죠.

 

예를 들어, 코어가 10개 있습니다. cores = [1,2,3,4,5,6,7,8,9,10] 이라고 해요. 근데, 작업해야 하는 수가 8이라고 한다면, 앞의 코어부터 작업을 쭉 할당하다가 마지막으로 작업을 처리하는 코어는 8번 코어가 되는 것이겠죠? 

 

 

# 2

그럼 처리해야 할 작업의 개수 n이 len(cores), 즉 CPU에 할당되어 있는 core개수보다 많을 때 어떻게 해야할지를 구현해야 하는 것이 이 문제의 핵심입니다.

 

저는 이 문제의 키워드는 "동시성"이라고 생각합니다. 작업시간을 나타내는 [1,2,3] 이라는 코어가 3개 존재할 때, 1시간이 흐르면 1번째 코어는 작업이 끝나서 일을 안합니다. 또 1시간이 흐르면, 2번째 코어도 작업이 끝나겠죠. 그럼 2시간이 지났을 때는 일을 하지 않는 코어가 (1번째 코어, 2번째 코어)로 2개가 되는 것입니다. 이러한 예시는 문제의 입출력 예시 설명에도 잘 나와 있습니다.

 

이제 본격적으로, 이분탐색을 이용해야 하는데, 우리는 작업 처리 시간을 알 필요가 있습니다.

n = 15, cores = [1,2,3,4,5] 의 예시를 그림으로, 한 번 표현해볼게요.

0h는 시작하자마자 모든 코어에 작업을 할당해줍니다.

1h => 처리시간이 1의 약수인 1 값을 갖는 코어에 작업이 추가되고,

2h => 처리시간이 2의 약수인 1,2 값을 갖는 코어에 작업이 추가되고,

3h => 처리시간이 3의 약수인 1,3 값을 갖는 코어에 작업이 추가되고,

4h => 처리시간이 4의 약수인 1, 2, 4 값을 갖는 코어에 작업이 추가되고,

5h => 처리시간이 5의 약수인 1,5 값을 갖는 코어에 작업이 추가됩니다.

...

보시는 것과 같이 규칙은 이렇습니다.

새로 추가되는 작업 수 = (시간(h)의 약수를 작업시간으로 갖는 코어들) 의 합

흐르는 시간(h)과 코어의 작업 처리시간이 얼마인지에 따라 답이 달라질 수 있습니다.

즉, 어떤 시간 h가 있을 때, 진행된 총 작업 수를 구할 수 있겠죠.

 

나머지 풀이는 이제 전체 코드를 보면서 확인해보겠습니다.

def solution(n, cores):
    
    answer = 0
    
    if n <= len(cores):
        answer = n
    else:
        n -= len(cores) # 처음 len(cores)개의 작업이 cpu에 들어갑니다.
        # start 는 1
        # end 는 코어들이 무조건 이 시간안에는 끝나는 시간
        start =  1
        end = max(cores) * len(cores)
        
        while start < end:
            mid = (start + end) // 2    # 중간 위치
            process = 0
            
            # 시간 당 수행하게 되는 프로세스의 갯수는 시간의 약수인 작업시간을 갖는 cpu들의 합입니다.
            # 이를 이용하여 mid시간까지 수행한 프로세스의 갯수가 n보다 크거나 같은 지점을 찾고, 
            # 남은 만큼을 순회하며 마지막 cpu를 찾았다.
            
            for core in cores:
                process += mid // core
            # print(process)
            if process >= n:
                end = mid
            else:
                start = mid+1
            
        for core in cores:
            n-= (end-1) //core
            
        for i in range(len(cores)):
            if end%cores[i]==0:
                # print(n)
                n-=1
                if n==0:
                    answer = i+1
                    break
    
    return answer

 

이진 탐색을 이용할 것인데, 우선 변수 start와 mid와 end는 시간(h) 값이 됩니다. 이 때, start는 1부터 시작하고, end는 cores 배열 중에 (가장 처리시간이 큰 core) x (코어의 수) 로 할당합니다. 예를 들어, [3,4,5] 이라는 배열이 있으면 작업은 최대 15시간안에는 끝날 것입니다. 그러니까, 가장 최대의 값을 임의로 잡은 것입니다.

 

mid는 말 그대로 start와 end의 중간값으로 설정하고, mid시간 까지 수행한 총 프로세스(process)가 타겟 작업수인 n 보다 크거나 같은 지점을 찾는 것이 목표입니다. 그리고, 이제 남은 만큼을 순회하면서 마지막 cpu번호가 몇번 코어 인지 찾는 셈이죠.

 

그러니까, n = 15, cores = [1,2,3,4,5] 의 예시를 다시 본다면,

4h까지의 작업 수가 13이므로, n-13 = 2, 즉 2 개의 작업만 더 실행되면 됩니다. 따라서, 4h에서 진행 가능한 cpu(코어) 중 두 번째에 있는 cpu(코어)인 5가 정답이 되는 것입니다.

 

다시 설명해서, mid시간 까지 수행한 총 프로세스(process)가 타겟 작업수인 n 보다 크거나 같은 지점을 찾는 것이 목표인 이유는 h - 1시간까지의 총 작업량을 구한 뒤에, h 시간의 cpu(코어)를 하나씩 진행가능한 상태인지 count하며 n의 값이 채워지면, 그 코어번호가 정답이 되는 것입니다.

 

코드를 다시 분석해봅시다.

def solution(n, cores):
    
    answer = 0
    
    if n <= len(cores):
        answer = n
    else:
        n -= len(cores) # 처음 len(cores)개의 작업이 cpu에 들어갑니다.
        # start 는 1
        # end 는 코어들이 무조건 이 시간안에는 끝나는 시간
        start =  1
        end = max(cores) * n
        
        while start < end:	# start가 end와 같아지면 while문 탈출
        
            mid = (start + end) // 2    # 중간 위치
            process = 0
            
            # 시간 당 수행하게 되는 프로세스의 갯수는 시간의 약수인 작업시간을 갖는 cpu들의 합임.
            # 이를 이용하여 mid시간까지 수행한 프로세스의 갯수가 n보다 크거나 같은 지점을 찾고, 
            # 남은 만큼을 순회하며 마지막 cpu를 찾습니다.
            
            for core in cores:
                process += mid // core	# process는 mid시간까지 처리할 수 있는 총 작업개수
            
            if process >= n:	# process가 n보다 크거나 같으면, end를 mid 로 줄여야 함
                end = mid	
            else:		# process가 n보다 작으면, start를 mid+1 로 늘려야 함
                start = mid+1
            
        for core in cores:
        	n-= (end-1) //core		# (end-1)시간까지의 진행된 총 작업수를 구하고 전체 n에서 뺀다.  
    
        for i in range(len(cores)):
            if end%cores[i]==0:		# end시간의 약수에 cores[i]가 포함된다면,
                n-=1				# 남은 작업 -1 ( 작업 할당)
                if n==0:			# 작업이 비로소 0 이 됐다면,
                    answer = i+1	# 해당 코어번호가 답(+1을 한 이유는 인덱싱이 0부터이므로)
                    break
    
    return answer

주석을 읽어내려가면서 코드를 보면 이해가 쉬울 것입니다.

가장 좋은 것은 코드를 토대로, 임의의 테스트케이스를 만들어서 종이에 써가면서 풀어보면 이해가 확 되겠죠?

 

여기서 해당 코드는 

for core in cores:
	n -= (end-1) // core 	# (end-1)시간까지의 진행된 총 작업수를 구하고 전체 n에서 뺀다.

아래와 같은 뜻입니다!

tmp = 0
for core in cores:
	tmp += (end-1) // core	# (end-1)시간까지의 진행된 총 작업수를 구하고 
n -= tmp	# 전체 작업 수 n에서 뺀다.(여기서 초기 n은 0h때 들어간 작업개수는 뺀 n)

 

(※ 끝으로, 해당 문제를 풀면서, 이진탐색 말고, 파라메트릭 서치 에 대해서도 접하게 됐습니다.해당 알고리즘은 구글링을 하다가, 아래 블로그에서 잘 정리된 것 같아 그대로 첨부해드리겠습니다.)

직관적으로 이해한대로 설명드리자면, 이진탐색과 거의 일맥상통하다는 느낌입니다..!

https://sarah950716.tistory.com/16

[이분탐색] 파라메트릭 서치(개념)

 

이상으로, 프로그래머스 - 선입 선출 스케줄링 문제에 대해 알아봤습니다!