[Python] 디스크 컨트롤러

[코딩테스트 고득점 KIT - 힙]

 

 

힙 파트 문제였지만,

jobs의 길이가 최대 500이기에 리스트와 정렬로 충분히 풀 수 가 있었다.

 

1. jobs 배열을 요청시간 기준으로 오름차순으로 정렬하기,
   요청시간으로 정렬하고 만약 같다면 소요시간을 기준으로 정렬
2. 테스크 처리 도중에 들어온 테스크들은 요청시간과 상관없이 소요시간 기준으로 정렬,
   이 경우가 각 작업의 요청부터 종료까지 걸린 시간의 평균  이 가장 적게 나온다.
3. 테스크 처리 도중이 아닌 경우에는 가장 첫 번째 값 처리

위 3 가지를 고려하여 코드를 작성하였다.

 

문제 속에서 2번 요구사항을 파악하는게 중요한 문제였지만,

3번 예외사항을 놓치고 있어서 19번 테케에서 통과를 못해 고생했다.

 

끝

 

def solution(jobs):
	
    # 작업 소요시간, 요청 시점을 오름차순으로 정렬
    jobs = sorted(jobs,key=lambda x: (x[0],x[1]))
    
    # 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
    answer = [jobs[0][1]]
    time = jobs[0][0] + jobs[0][1]
    l = len(jobs)
    jobs.pop(0)
    
    while(jobs):
    	# sp_t : 소요시간, idx : 작업 인덱스
        sp_t = 0
        idx = 0
        
        for job in jobs:
        	# 작업 시점이 소요된 시간보다 큰 경우는 패스
            if job[0] > time:
                break
            # 작업 시점을 초과한 경우
            elif (job[0] <= time):
            	# 예상 소요시간 초기화
                if sp_t == 0:
                    sp_t = job[1]
                # 소요시간이 가장 작은 작업을 찾기
                elif sp_t > job[1]:
                    sp_t = job[1]
                    idx = jobs.index(job)
        # 소요시간이 가장 작은 작업 수행
        if sp_t != 0:
            answer.append(jobs[idx][1]+time-jobs[idx][0])
            time += jobs[idx][1]
            jobs.pop(idx)
        # 작업 시점이 앞선 작업의 소요시간보다 큰 경우
        elif sp_t == 0:
            next_job = jobs.pop(0)
            answer.append(next_job[1])
            time += next_job[1]
    
    # 소수점은 버린다.
    return sum(answer)//l