300x250
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 코딩
- 킥스타트
- 리눅스
- BFS
- 동적프로그래밍
- 알고리즘
- kick start
- 네트워크
- linux
- 운영체제
- 파이썬
- 백준
- DFS
- AI
- dp
- 구글 킥스타트
- 브루트포스
- 그래프
- PYTHON
- 순열
- 딥러닝
- google coding competition
- nlp
- 코딩테스트
- 코딩 테스트
- 프로그래밍
- OS
- 동적 프로그래밍
- 프로그래머스
- CSS
Archives
- Today
- Total
오뚝이개발자
디스크 컨트롤러 본문
728x90
300x250
문제
문제가 조금 복잡해서 링크를 첨부하겠다.
programmers.co.kr/learn/courses/30/lessons/42627
풀이
전공자거나 운영체제의 스케쥴링 부분을 공부한 사람이라면 소요시간이 작은 작업을 우선적으로 처리하는 것이 최적의 경우라는 것을 알 것이다. 우선순위큐를 이용하면 되는데 약간은 복잡한 조건을 고려해주어야 한다. 그러나 단순히 소요시간 기준으로 정렬해 처리하면 다른 조건들을 고려하지 못한다. 생각의 순서는 다음과 같다.
-
요청시점 순으로 오름차순 정렬 후 소요시간 순으로 오름차순 정렬을 해 첫 번째 원소를 첫 번째 작업으로 할당
-
하나의 작업을 배정하는 매 순간 현재 시간을 계산해준다.(예컨대, 첫 번째 작업의 요청시간이 0, 소요시간이 3이라면 첫 번째 작업 배정 후 현재시간은 3이다.)
-
반복문으로 탐색하며 '현재 시간에서 가능한 작업' 중 소요시간이 짧은 것을 우선적으로 배정한다.
-
이 때, 주의할 점이 현재시간이 요청시간이 가장 빠른 작업의 요청시점보다 작은 경우는 현재시간을 해당 작업의 요청시점으로 갱신한다.(예컨대, 현재시간은 3인데 요청시간이 가장 빠른 작업의 요청시점이 5라면 시간이 더 지나야 작업을 할당할 수 있기 때문에)
def solution(jobs):
answer = 0
# 요청시점 순으로 오름차순 정렬 후 소요시간 순으로 오름차순 정렬
s_jobs = sorted(jobs, key = lambda x : (x[0],x[1]))
now_time = 0 # 현재 시간 기록
first_job = s_jobs.pop(0)
now_time = first_job[0]+first_job[1]
answer += now_time - first_job[0]
s_jobs = sorted(s_jobs, key = lambda x : x[1])
while s_jobs:
temp = sorted(s_jobs, key = lambda x : x[0])
if now_time < temp[0][0]:
# 요청시간이 가장 빠른 작업의 요청시간보다 현재 시간이 더 작은 경우
now_time = temp[0][0]
for job in s_jobs:
if job[0] <= now_time:
now_time += job[1]
answer += now_time - job[0]
s_jobs.remove(job)
break
return answer//len(jobs)
728x90
300x250
Comments