[프로그래머스] 힙, 디스크 컨트롤러

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

프로그래머스

문제 개요

 

input
: jobs = [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열

return
: 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마
*소수점 이하의 수는 버림

*하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리

 

문제 이해

 

input:  [[0, 3], [1, 9], [2, 6]]

 

우측보다 좌측의 경우, 프로세스 총소요시간(요청부터 처리될 때까지 총시간)의 평균이 적다.

return: 9 (총 27 // 3)

 

문제 결론

• 대기 시간이 없는 경우와 있는 경우를 구분한다.
  • 대기 시간이 있는 경우 if문 내부에서 현재 시각 now를 조절함으로써, '대기 시간이 없는 경우'와 state를 일치시킨다.
  • 현재 시각 now 계산 식 & 프로세스 총 소요시간 계산 식을 if문 외부에서 공유: waitlst의 heappop 처리.
• 대기 시간이 없는 경우: 소요 시간이 짧은 것을 우선순위로 처리 → heappop (자동 min 정렬)
  • jobs에서 원소를 하나씩 꺼내어 waitlst에 heappush. 즉 jobs 대신 waitlst를 heap으로 처리. 
• 대기 시간이 있는 경우: jobs에서 가장 이른 것을 꺼내어 waitlst에 heappush.

자주 활용되는 아이디어이므로 확실히 기억할 것

 

문제 이해 프로세스

1. 작업의 요청부터 종료까지 걸린 시간 = 기다린 시간(변수) + 프로세스 진행 시간(상수)

2. '기다린 시간(변수)'은 해당 프로세스가 요청된 시각이 직전 프로세스 종료 시각보다 '이전인가' '이후인가'에 따라 계산 방법이 다르다.

→ 시각과 시간 구분하자

→ 직전 종료 시각을 어떻게 구하는가..? (생각의 무한루프 ♾️🥲)

→ 초깃값은 어차피 a가 가장 작은 값으로 결정되어 있으니 이후 점화식 잘 세우면 된다 (ps: 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리)

 

→ 일단 '기다린 시간'을 경우에 따라 나누어보자. (경우 = if문으로 구현)

→ 처음에는 '직전 프로세스 종료 시각'을 end로 지정했는데, 오히려 헷갈려서, 현재 시각 'now'로 대체하였다 **

 

현재 프로세스: [a,b]

1️⃣ if 현재 시각(now) >= 현재 프로세스 요청 시각:

기다린 시간 = 기존 now - a

프로세스 총 소요시간 = (기존 now-a) + b == (업데이트 완료한 now) - a

프로세스 끝난 후 현재 시각 업데이트 now = 기존 now+b

 

2️⃣ elif 현재 시각(now) < 현재 프로세스 요청 시각:

기다린 시간 = 0

프로세스 총 소요시간 = b == (업데이트 완료한 now) - a

프로세스 끝난 후 현재 시각 업데이트 now = a+b

 

3. 그런데 어떻게 정렬하지.. (생각의 무한루프 ♾️🥲 again)

끄적이다 겨우 알아낸 사실:

- 상수인 것을 제외하고 변수인 것을 비교하자. 

- 프로세스 소요시간이 짧은 것부터 정렬해야 한다.

- 조건에 의해, 작업을 수행하고 있지 않을 때에는, 먼저 요청이 들어온 작업부터 처리해야 하므로 → 현재 시각 이전에 요청된 프로세스 먼저 처리하고 → 나머지를 처리해야 한다.

 

- 현재 시각 이전에 요청된 프로세스 즉 대기 중인 프로세스를 waitlst에 저장 1️⃣

- 단, 대기 중인 프로세스가 없는 경우도 있다! 2️⃣ 

 

▶ waitlst가 비어 있지 않은 경우 1️⃣
    → jobs 리스트에서 소요시간이 가장 짧은 것을 먼저 waitlst에 heappush
    → 단 waitlst 내부에서는 '소요시간'을 기준으로 정렬해야 하므로, for문 heappush 시 인덱스 위치를 바꾼 채로.

▶ waitlst가 비어 있는 경우(=요청이 가장 이른 다음 프로세스가 현재 시각 이후에 요청될 때) 2️⃣ 
    → 시각을 옮겨주어 다음 프로세스가 바로 시작될 수 있도록 세팅한다: now = 요청시각
    → 가장 이른 프로세스를 jobs 리스트에서 heappush, 마찬가지 인덱스 위치를 바꾼 채로.

▶ 1️⃣&2️⃣ 거친 후
→ now += 소요시간
→ 프로세스 총 소요시간: now - 요청시각
→ total.append(now - 요청시각)

▶ 서로 다른 계산식을 가지는 1️⃣&2️⃣를 잘 처리함으로써 결과적으로 동일한 state가 되도록 일치시킴
→ now 및 total 계산식을 간단히 공유할 수 있게 됨.

▶ 마무리: int(total / len(jobs)) OR total // len(jobs)

*소수점 이하의 수는 버림 조건 매우 주의
*조건 상 분모가 0이 될 수 없으므로 해당부분은 pass.

 

 

나의 코드

from heapq import heapify, heappop, heappush

def solution(jobs):
  j_len = len(jobs)
  heapify(jobs)
  now = 0
  total = []
  waitlst = [] #waitlst의 위치 중요

  while len(total)<j_len:
    while jobs and (jobs[0][0] <= now):
        next = heappop(jobs)
        heappush(waitlst, (next[1],next[0]))

    if jobs and waitlst == []:
      next = heappop(jobs) #jobs에서 다음 활동 next 직접 꺼내기
      now = next[0] #next 진행되도록 시간 세팅
      heappush(waitlst, (next[1], next[0])) #next를 waitlst에 직접 추가
    
    x,y = heappop(waitlst)
    now += x #프로세스 진행하였으므로 진행시간 포함하여 현재 시간 업데이트 
    total.append(now-y)
  
  answer = sum(total)//j_len
  return answer

• 현재 시각 now의 업데이트 아이디어 중요 ⭐
• indentation & while문 & if문 조건 엄밀하게 설정해야 함 ⭐
• 리스트를 heap으로 변환 안 하더라도, 리스트 자체로 heappop 바로 쓸 수 있구나.
• jobs는 리스트 그대로 두고, wait할 원소를 pop하기만 함 → waitlst에서 사용되지 않은 원소를 jobs로 되돌릴 필요 없음
• waitlst가 heap이며, waitlst 내에 새로운 원소가 들어올 때마다 힙정렬. (heappop, heappush 시 자동 힙정렬)
• waitlst가 비어있을 때 jobs 리스트 첫번째 원소의 시작 시간으로 now를 맞춤 

while len(total)<j_len:

• 이때 while jobs 하면 안 됨. jobs가 모두 pop되어 빈 리스트가 되더라도, waitlst에는 처리할 작업이 남아 있을 수 있음.

while jobs and (jobs[0][0] <= now):

• "jobs 리스트가 비어있지 않고" and "jobs[0][0] <= now" 동안에 계속.

if jobs and waitlst == []:

• "jobs 리스트가 비어있지 않고" and "waitlst는 비어있을 때" 한번.

heappush(waitlst, (next[1],next[0]))

• heap은 기본적으로 원소의 0index를 기준으로 정렬하므로, 이같이 인덱스 뒤집어 힙정렬 처리 필요.

 

 

다른 코드

import heapq

def solution2(jobs):
    answer, now, i = 0, 0, 0
    start = -1 
    heap = []
    
    while i < len(jobs):
        # 현재 시점에서 처리할 수 있는 작업을 heap에 저장
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])
        
        if len(heap) > 0: # 처리할 작업이 있는 경우
            cur = heapq.heappop(heap)
            start = now
            now += cur[0]
            answer += now - cur[1] # 작업 요청시간부터 종료시간까지의 시간 계산
            i +=1
        else: # 처리할 작업이 없는 경우 다음 시간을 넘어감
            now += 1
                
    return answer // len(jobs)

 

왜 틀렸을까 .. 19번 실패

19번 관련 테스트케이스 모두 통과인데,,

아래 코드!

from heapq import heapify, heappop, heappush
from collections import deque

def solution(jobs):
  j_len = len(jobs)
  heapify(jobs)

  end = 0
  total = 0
  while jobs:
    waitlst = []

    while jobs[0][0] <= end:
        a = heappop(jobs)
        waitlst.append(a)
        if len(jobs) == 0:
            break

    if waitlst:
      waitlst.sort(key=lambda x: x[1])
      waitlst = deque(waitlst)
      next = waitlst.popleft()

      end+= next[1]
      present = (end-next[0])
      for i in waitlst:
        heappush(jobs, i)

    else:
      next = heappop(jobs)
      end += (next[0]+next[1])
      present = next[1]

    total += present

  answer = int(total/j_len)
  return answer