[프로그래머스][힙] 디스크 컨트롤러
1. 문제설명
| 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. |
2. 제안사항
- jobs의 길이는 1이상 500 이하입니다.
- jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
- 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
- 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
- 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
3. 입출력 예
| jobs | return |
| [[0, 3], [1, 9], [2, 6]] | 9 |
4. 풀이 과정
이 문제를 볼때 가장 처음 생각난것은 '그리디 알고리즘'이다.
그리디 알고리즘이란 그 순간 최적의 선택만을 고르는 알고리즘이다.
실제로 문제의 입출력 예에서 시작 할 수 있는 시점에서
가장 좋은(가장 작업 시간이 적은) 것을 선택하는 것이다.
오히려 힙보다는 그리디 알고리즘에 적합하지 않은가 싶었다.
추 후 문제풀고 다른 사람들의 풀이를 보니 힙을 이용하는 사람들은 있지만 필자는 그런 방식을 사용하지 않았다.
우선 문제를 봤을 때 크게 2가지를 고려했다.
1. 가장 최적의 값을 선택한다.
2. 최적의 값의 요청되는 시점이 그 작업이 실행 되는 시점보다 이전인가?
그렇기 때문에 time이라는 변수를 따로 선언하여 2번 문제를 해결하였고, sort를 이용하여 정렬해서 1번 문제를 해결하였다.
처음에는 정렬된 리스트를 반복문으로 탐색하면서 그 작업요청이 time보다 같거나 이전 시점이면 그거를 바로 answer과 time에 반영하고 리스트에서 삭제한다.
어차피 작업 시간이 짧은 것들은 앞쪽으로 정렬되어 있기 때문에 가능하다.
그리고 time의 값이 변동되었기 때문에 처음 인덱스값부터 살펴본다.
만약 그렇지 않은 경우 다음 인덱스를 살펴보기 위해서 i의 값을 증가시켜둔다.
이런 방식이 테스트 코드에서는 문제없이 작동했는데, 이가 실제로 제출하니까 런타임 에러가 난다.
이 방식에는 런타임 에러가 나올만한 경우는 오로지 인덱스를 오버하는 경우밖에 없기 때문에 elif len(jobs) - 1 > i: 라는 조건을 추가적으로 넣어서 이런 경우를 방지하였다.
하지만 런타임 에러가 지속적으로 발생하였고, 예외 케이스를 고민해봤다.
생각보다 간단한데 예외 케이스는 현 시점에서 작업을 할 수 없을 때 였다. 그래서 이 역시 조건문에 넣어줌으로써 문제를 해결하였다.
이런 문제를 생각했을 때 time의 init값으로 첫번째 작업값의 시작지점을 넣어주는것도 고려해봤지만, 난 위에서 작업에 걸리는 시간만을 고려해서 정렬하였기 때문에 [1,6],[0,7] 같은 경우에는 부적절하다 생각하여 그만두었다.
def solution(jobs):
answer = 0
jobs_len = len(jobs)
jobs.sort(key = lambda x : x[1])
time = 0
i = 0
while len(jobs) > 0:
if time >= jobs[i][0]:
time += jobs[i][1]
answer += time - jobs[i][0]
jobs.pop(i)
i = 0
elif len(jobs) - 1 > i:
i += 1
else:
time += 1
i = 0
return answer // jobs_len