728x90
반응형
문제:
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.
예를 들어,
0ms 시점에 3ms가 소요되는 A작업 요청
1ms 시점에 9ms가 소요되는 B작업 요청
2ms 시점에 6ms가 소요되는 C작업 요청
과 같이 요청이 들어왔습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.
A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)
이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(=(3+11+16)/3)가 됩니다.
하지만 A->C->B 순서대로 처리하면
A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
B: 2ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)
이렇게 A->C->B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(=(3+7+17)/3)가 됩니다.
각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마나 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소주점 이하의 수는 버립니다)
풀이 방법:
위에서 처음 소개한 방법은 FCFS 방법으로 먼저 들어오는 작업을 먼저 수행하는 것으로 긴 작업이 먼저 들어올 경우 뒤에 들어온 작업들이 수행하기까지 많은 시간을 대기하기 때문에 평균시간이 길어지게 된다. 따라서 이를 해결하기 위해서 후자의 방법인 SJF를 사용하는 것이다. 즉 짧은 요청을 먼저 수행하는 것이다. 별도의 정렬이 없어도 작은 값을 반환해줄 수 있는 힙 구조를 사용해서 이 문제를 풀어야 한다.
last와 now라는 두 변수를 사용해서 하나의 작업이 들어간 시점과 나오는 시점을 구분해준다. 또한 이 두 변수를 이용해 구간을 구성하고 이 구간 사이에 있는 jobs들을 heap에 담도록 한다. heap에 담기전에 now에서 그 작업이 들어온 시점부터까지의 시간을 계산해서 더해준다.
'C와 B의 작업은 A가 수행되고 있는 도중에 들어오게 되었으며, A가 끝나는 시점인 3ms 까지 각각 1ms, 2ms를 대기한다.'
또한 len(wait)와 wait[0]을 곱한 값을 더하기도 한다. 이 말은 다음과 같다.
'C가 수행되는 동안에 B가 이미 들어와 있어서 같이 대기를 해야 한다. 즉 C의 수행시간인 6ms 만큼 B가 대기하고 있다. 총 12ms 만큼 시간이 더해져야 한다.'
와 같은 말이다.
count 변수를 만들어서 이 변수가 jobs의 길이와 같이 지는 순간까지 반복하면 각 작업들이 총 수행되는 시간을 알 수 있고 이를 jobs의 길이로 나누어 준 몫을 구하면 평균을 구할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | import heapq def solution(jobs): last=-1 now=0 answer=0 wait=[] n=len(jobs) count=0 while(count<n): for job in jobs: if last <job[0]<=now: answer+=(now-job[0]) heapq.heappush(wait,job[1]) if len(wait)>0: answer+=len(wait)*wait[0] last=now now+=heapq.heappop(wait) count+=1 else: now+=1 return answer//n | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]11050. 이항 계수 1 (0) | 2019.05.08 |
|---|---|
| [BOJ]11866. 조세퍼스 문제0 (0) | 2019.05.07 |
| [BOJ]8979. 올림픽 (0) | 2019.05.05 |
| [BOJ]1076. 저항 (0) | 2019.05.04 |
| [BOJ]1977. 완전제곱수 (0) | 2019.05.03 |