과제 진행하기

https://school.programmers.co.kr/learn/courses/30/lessons/176962

프로그래머스

문제 요약:

과제가 시작 시간과 소요시간이 주어진다, 시작시간대로 시작하다가 끝나기전에 새로운과제 시작시간이 된다면 하던 과제를 멈추고 새로운과제를 이어서 한다고 했을때 과제가 끝나는 순서를 반환하라.

 

소요시간:

40분 + 20분

난이도 2

 

코딩:

from collections import deque
def solution(plans):
	for i,plan in enumerate(plans):
		plans[i][1] = int(plan[1][:2])*60 + int(plan[1][3:])
		plans[i][2] = int(plan[2])
	plans.sort(key = lambda x : x[1])
	plans = deque(plans)

	q = []
	result = []

	while plans:
		if q == []:
			q.append(plans.popleft())
		else:
			name,t1,t2 = q.pop()
			if t1+t2 <= plans[0][1] : #만약 리스트에 있는것보다 새로운게 더 늦는다면
				result.append(name)   #최신 리스트는 나옴
				for i in range(len(q)):
					q[i][1]=t1 +t2    #리스트내의 시간 초기화
			else: 					  #리스트가 더 느림 새로운게 빨라
				t2 = t1+t2 -plans[0][1] #지난 시간만큼은 깎아줌
				q.append([name,t1,t2]) #다시넣고
				q.append(plans.popleft())
	for i in range(len(q)-1,-1,-1):
		result.append(q[i][0])
	return result

먼저 문자열 데이터 타입이기 때문에, 문자열을 모두 숫자로 바꿔주고, 시작시간 기준으로 재정렬 해줍니다. 

그 후 원래있던 데이터와 새로운데이터를 계속 비교해 먼저 끝나는것을 결과에 넣어줍니다. 이때 만약 새로운것이 더 느릴때 q에 다시 넣는것이 아니라 q에 있던데이터만 꺼내주고 다시 재 비교를 해야 정확한 비교가 가능합니다.

 

다른사람 코드:

def solution(plans):
	#똑같이 숫자로 바꾼후 역순으로 정렬(이렇게 하면 deque로 바꿀 필요없이, pop으로 사용가능)
	plans = sorted(map(lambda x: [x[0], int(x[1][:2]) * 60 + int(x[1][3:]), int(x[2])], plans), key=lambda x: -x[1])
	lst = []
	while plans:
		x = plans.pop()
		for i, v in enumerate(lst):
			#먼저 들어간 리스트를 훑으면서
			#먼저시작했는데 새로 들어가는거보다 늦게끝난다면
			if v[0] > x[1]: 
				#먼저시작한것들 끝나는시간 새로시작하는거만
				lst[i][0] += x[2]
		#리스트에 끝나는 시간 , 이름
		lst.append([x[1] + x[2], x[0]])
	lst.sort()
	return list(map(lambda x: x[1], lst))

주석을 새로 달았지만, 쉽게말하면 시작시간 기준으로 정렬하고, 그다음것과 끝나는시간기준으로 비교할때 안끝났다면 무조건 새로운것의 시간만큼 추가시키는 로직입니다. 사실 제가 푼것은 문제에서 말한것을 구현한것에 가까운데 이렇게 풀어야 그리디로 풀었다고 할 수 있을것 같습니다. 

또한 sorted(map(lambda x :[ ~ ],list),key ~) 이 코딩은 어떤 리스트의 형식을 바꾸고 재정렬할때 매우 간단하게 쓸 수 있을것 같아 눈여겨 볼만 한것 같습니다.