내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
디스크 컨트롤러
ps:problems:programmers:42627
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 디스크 컨트롤러 ====== ===== 풀이 ===== * 일종의 스케쥴링 문제이다. 보통 그리디로 많이 풀리기는 하는데, 조건이 조금씩 바뀔때마다 어떤 것을 먼저 선택해야 할지 기준도 달라져서, 경우에 따라서는 꽤나 어려울 때도 있다. 다행히 이 문제는 별로 어렵지 않게, 대기중인 작업중 소요시간이 가장 작은 작업부터 시작하면 된다. * 항상 그리디는 엄밀하게 증명하려면 복잡해진다. 간략히 설명만 하면.. * 진행중인 작업이 없을때, 이미 요청이 들어와있는 작업을 시작하지 않고 기다리는 것은 최적해가 될 수 없다. (증명 생략) * 진행중이던 작업X가 끝난 시점에서, A,B 작업에 대한 요청이 들어와 있었다고 하자. A와 B중 어떤 요청이 먼저 들어왔는지는 중요치 않다. 각 작업에 대해 여태까지 대기했던 시간은 이미 지나가버린거라서 바꿀수 없고, 지금 시점부터 종료시간까지의 합을 최소화 하는게 중요하다. T(A), T(B)를 A의 소요시간과 B의 소요시간이라고 하면, A를 먼저 하고 A가 끝나면 바로 B를 한다고 했을때, A가 종료까지 걸리는 시간은 T(A), B가 종료까지 걸리는 시간은 T(A)+T(B), 둘의 합은 2T(A)+T(B). 반대로 B를 먼저 하면 합은 T(A)+2T(B). T(A)<T(B)일 경우에는 A를 먼저하는 것이 더 효율적이다. 같은 원리로 대기중인 작업이 A,B 2개가 아니라 더 많은 경우에도 가장 소요시간이 적은것부터 처리하면 된다. * 구현은 그냥 이대로 하면 된다. 대기중인 작업을 우선순위큐를 이용해서 관리하면, 소요시간이 가장 작은 작업을 O(logn)에 찾을 수 있다. * 처음에 작업들을 요청 시간을 기준으로 정렬해야 하니까 O(nlogn)이 걸리고, 그 뒤 n개의 작업들이 한번씩 우선순위큐에 push되었다가 pop되어야 하므로 이것도 전부 O(nlogn)이 든다. 결국 총 시간복잡도도 O(nlogn) ===== 코드 ===== <dkpr py> """Solution code for "Programmers 42627. 디스크 컨트롤러". - Problem link: https://programmers.co.kr/learn/courses/30/lessons/42627 - Solution link: http://www.teferi.net/ps/problems/programmers/42627 """ import heapq def solution(jobs): total_time = 0 current_time = 0 job_count = len(jobs) jobs.sort(reverse=True) job_heap = [] for _ in range(job_count): while jobs: requested_time, execution_time = jobs[-1] if requested_time > current_time: break heapq.heappush(job_heap, (execution_time, requested_time)) jobs.pop() if job_heap: execution_time, requested_time = heapq.heappop(job_heap) current_time += execution_time else: requested_time, execution_time = jobs.pop() current_time = requested_time + execution_time total_time += current_time - requested_time return total_time // job_count </dkpr> {{tag>프로그래머스 ps:problems:programmers:Level_3}}
ps/problems/programmers/42627.txt
· 마지막으로 수정됨: 2021/05/28 03:11 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로