[프로그래머스] 과제 진행하기 (정렬, 시간 문자열 비교)

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

프로그래머스

 

분석

1. 과제를 시작 시간 순으로 정렬
2. 과제의 시작시간을 분단위로 통일해서 저장 (ex: 11:40 → 11*60+40 = 700)
3. 과제를 돌면서 현재 과제 종료시간과 다음 과제의 시작시간 비교
   1. 현재 과제 종료시간이 더 크다면 (안끝남)
      1. playtime(과제 마치는데 필요한 시간)에서 수행한 시간( 다음 과제 시작시간-현재 과제 시작시간) 만큼 빼서
      2. 대기 큐에 저장
   2. 현재 과제 종료시간이 더 작다면 ( 끝남)
      1. 정답 리스트에 과제 이름 추가
      2. 여유시간 계산 ( 다음과제 시작시간 - 현재 과제 종료시간)
      3. 여유시간이 있고 대기 큐에 대기중인 과제가 있다면
         1. 가장 최근에 멈춘 과제부터 돌려서
            1. 여유시간 내로 완료 된다면 대기큐에서 pop, 정답 리스트에 과제 이름 추가
            2. 여유시간 내로 완료 되지않는다면 대기큐의 멈춘 과제 수행시간에 여유시간 빼기
4. 대기 큐에 멈춘 과제가 남아있다면 정답 리스트에 과제 이름 추가
5. 정답 리스트 리턴

 

풀이

def solution(plans):
    answer = []
    wait = []

    plans.sort(key=lambda x: x[1])

    for p in plans:
        name, start, playtime=p
        h, m = map(int, start.split(":"))
        p[1] = time=h*60+m
        p[2] = int(p[2])

    for i,(n,s,p) in enumerate(plans):
        end = s + p # 종료시간

        if i == len(plans)-1:
            answer.append(n)
        else:
            next_start = plans[i+1][1] # 다음 시작 시간

            if end > next_start: # 안끝남
                p-=next_start-s
                wait.append([n, p])

            else: # 끝남
                answer.append(plans[i][0])

                left = next_start-end # 여유시간
                if wait and left > 0:
                    temp = wait[:]
                    for x in range(len(temp)-1, -1, -1): # 가장 최근에 멈춘 과제부터
                        name, playtime = temp[x]
                        if playtime <= left: # 여유시간 내에 오나료
                            wait.pop(x)
                            answer.append(name)
                            left -= playtime
                        else:
                            wait[x][1]-=left
                            break

    for item in wait[::-1]:
        answer.append(item[0])

    return answer

 

 

2023.06.09 - [Algorithm PS/Greedy] - [2457] 공주님의 정원

[2457] 공주님의 정원