프로그래머스 코딩테스트 고득점 Kit : 힙 part - (프로그래머스 42627번 : 디스크 컨트롤러)

해당 문제는 프로그래머스에서 제공된 문제입니다.

힙 파트를 푸는 도중 난이도가 좀 있는 문제가 있어 기록하려 한다. 내가 풀었던 방식에 대해 설명하고 내가 막히고 잘못 풀었던 부분에 대해서도 설명하겠다.

[문제 설명]

코딩테스트 연습 - 디스크 컨트롤러

먼저, 이 문제가 요구하는 것이 무엇이고 이를 어떻게 접근해야 되는지 파악해보자. 일단 이문제는 '작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지'를 원하고 있다. 하지만 이 요구사항만 본다고 바로 접근 방식을 파악할 수 있는 것은 아니다. 파악을 위해선 예시를 차근차근 살펴보며 어떤 방식으로 접근해야 될지 정해야 한다. 예시에서 보면 일반적인 순서보다 가동 시간 자체가 짧은 순서로 가동 했을 때 걸린 시간의 평균을 가장 줄일 수 있다는 힌트를 준다. 하지만, 이를 통해서 그저 정렬을 통해서 짧은 순서로만 판단 하면 안 된다. 어찌 됐든 이 문제는 최솟값을 계속해서 추출해야 하고 또 효율적이게 풀기 위해서는 heap을 사용해야 한다. 그럼 이러한 부분들을 상기시켜 코드를 구현하며 더 깊게 설명하겠다.

---

[문제 풀이]

import heapq
import sys

# 시간을 기준으로 해당 시간에 들어온 요청 중 가장 작은 가동시간을 가지고 있는 디스크를 선택
def solution(jobs):
    time = 0  # 시간
    total = 0  # 평균 내기 위한 총합
    heap = []  # 그 시점의 가장 작은 가동시간을 판단하기 위해 heap사용
    check = 0  # 모든 디스크를 둘러봤는지 판단하기 위한
    N = len(jobs)  # 총 디스크의 수

    while True:
        # 모든 디스크를 둘러봤으면 반복문에서 나가기
        if check == N:
            break
        # 현재 시점까지 들어온 요청들을 heap에 추가
        for i in range(N):
            if jobs[i][0] <= time:  # 현재 시점안에 들어온 요청인지 판단
                heapq.heappush(heap, [jobs[i][1], jobs[i][0]])  # 가동시간과 요청시간을 함께 저장 (추후 계산에 이용)
                jobs[i][0] = sys.maxsize  # 현재 추가한 디스크는 이후에 비교대상이 아니므로 제외시켜줌
        if not heap:  # 요청이 아무것도 들어오지 않았다면
            time += 1  # 다음 시간
            continue
        min = heapq.heappop(heap)  # 현재 heap에 들어온 것 중 최소 가동시간을 추출
        check += 1  # 가동 디스크 수 추가
        time += min[0]  # 가동시간
        total += time - min[1]  # 요청 ~ 가동 끝

    return int(total / N)  # 평균 값 도출

이 문제는 어떻게 접근하냐에 따라 풀이가 천차만별이다. 물론 대부분의 공통사항은 시간을 기준으로 반복문을 진행했다는 점이다. 그 이후로 어떻게 처리하냐에 따라 풀이가 달라진다. 또한, 이 부분부터가 핵심이다. 나는 시간을 기준으로 돌면서 현재 시점에서 받거나 받았던 요청들 중 가동시간이 가장 적은 디스크를 선택했다. 앞서 말했던 부분이 이 부분이다. 그냥 최소 가동시간으로 돌리면 안 되고 항상 그 시점에서의 요청이 들어온 것들 중에서 최솟값을 판단해야 한다. 이러한 아이디어만 생각해 낸다면 어렵지 않게 구현할 수 있는 문제이다.

---

[잘못된 풀이 및 실수했던 점]

내가 처음 접근했던 방법은 최적의 해를 구하기보다는 모든 경우에 대해서 판단하고 최소 평균값을 반환하려 했다. 결론적으로는 잘못된 풀이였다. 애초에 모든 경우에서 판단하기에는 시간 복잡도가 굉장히 안 좋았고 또한, 하드디스크가 일하지 않을 때 들어오는 요청에 대해서 무조건 가동해줘야 한다는 조건을 만족할 수가 없었다. (문제도 안 읽음) 이런 식으로 구현하다 보니 구현하는데도 복잡하여 1시간 정도를 날린 것 같다. 그 후 최적의 평균값을 구해야 된다는 것을 인지하고 위의 풀이 방식대로 풀어나갔다. (그 와중에 또 조건을 제대로 안 읽어서 시간 버림). 이번 문제를 통해서 깨달은 점은 항상 다짐하는 얘기지만, 문제를 꼼꼼히 잘 읽자... 이다. 또, 잘못된 풀이에 빠지는 순간 이 문제에 대한 시간은 모두 날아간다는 점이다. 난이도가 높을수록 제대로 된 풀이 방식을 찾는 것도 어렵지만 또한 잘못된 풀이를 구현하는 것 자체도 오래 걸린다는 점이다. 결국은 깊게 자세히 읽고 제대로 파악하는 연습이 더 필요한 것 같다. (또, 빠르게 푸는 방법도!!!)