[프로그래머스] Lv2. 과제 진행하기

📝 문제

풀이

💡 아이디어

✅ 가장 최근에 멈춘 과제부터 시작

최근에 입력된 값부터 출력되는 스택 자료구조를 활용해서 도중에 멈춘 과제들을 저장한다.

✅ 새로운 과제 시작시간을 기준으로 판단

현재 과제가 진행중이어도 새로운 과제 시작 시간이 되면 중단하고 새로운 과제부터 처리하게 된다. 만약 현재 진행중인 과제가 새로운 과제 시작 시간 전에 종료된다면 answer에 추가한다. 만약 현재 진행중인 과제 종료 시간과 새로운 과제 시작 시간 사이에 여유 시간이 생긴다면 가장 최근에 멈춘 과제부터 진행한다

‼️ 현재 진행중인 과제와 새로운 과제 시작 시간 사이에 여유 시간이 생겼지만 도중에 멈춘 과제가 없는 경우

이 경우는 현재 시간을 다음 과제 시작 시간에 맞춰야 한다. (1) 현재 과제의 종료 시간과 (2) 다음 과제 시작 시간이 있는데 (1) ~ (2) 사이의 시간에 처리해야 될 과제가 없기 때문에 현재 시간을 (2)로 업데이트 해야 하는 것이다. 만약 이 처리를 해주지 않으면 다음 과제의 처리 시작 시간이 (1)로 설정되어서 제대로 된 결과가 나오지 않음

인덱스를 활용한 풀이

스택 배열을 따로 만들지 않고 plans 자체에서 인덱스 값을 조절하고 완료된 과제들은 pop으로 제거했다.

만약 하나의 과제가 종료되면 배열에서 제거하고, 여유 시간이 생기면 인덱스 값을 앞으로 한 칸씩 이동해서 과제를 진행한다. 인덱스가 0인 경우에는 앞으로 이동하지 않는다.

과제가 종료될 수 없다면 따로 스택 배열에 저장하는 대신에 playtime의 값을 업데이트하고 인덱스를 한 칸 뒤로 이동했다.

def solution(plans):
    answer = []
    
    for i in range(len(plans)):
        h, m = map(int, plans[i][1].split(':'))
        plans[i][1] = int(h)*60+m
        plans[i][2] = int(plans[i][2])
        
    plans.sort(key=lambda x: x[1])
    plans.append([" ", 1e13, 0])
    
    now, idx = plans[0][1], 0
    while idx < len(plans)-1:
        next = plans[idx+1][1]
        # 과제 수행 시간이 다음 과제 시작 시간을 넘어선다면
        # 일부만 수행하고 다음 과제부터 시작
        if now + plans[idx][2] > next:
            plans[idx][2] -= (next-now)
            idx += 1
            now = next
            continue
        
        _subject, _, _playtime = plans.pop(idx)
        answer.append(_subject)
        # 현재 과제 수행하고 now 업데이트
        now += _playtime
        if idx > 0:
            idx -= 1
        else:
            now = plans[idx][1]
        
            
    return answer

⭕️ 스택을 활용한 풀이

스택을 만들어 멈춘 과제들을 스택에 추가했다. 현재 과제를 진행하고 남는 여유 시간이 있다면 스택을 돌면서 새로운 과제 시작 시간 전까지 과제들을 진행한다. 스택이 비어 있다면 이 과정은 진행되지 않는다.

인덱스를 활용한 풀이보다 조금 더 빠르다.

def solution(plans):
    answer = []
    
    plans = list(map(lambda x: [x[0], int(x[1][:2])*60 + int(x[1][3:]), int(x[2])], plans))
    plans.sort(key=lambda x: x[1])
    plans.append([" ", 1e9, 0])
    
    stack = []
    for i in range(len(plans)-1):
        name, start, playtime = plans[i]
        next_start = plans[i+1][1]
        
        if start + playtime > next_start:
            stack.append([name, playtime - next_start + start])
            continue
            
        answer.append(name)
        start += playtime
        while stack and start < next_start:
            if stack[-1][1] > next_start - start:
                stack[-1][1] -= (next_start - start)
                break
            
            start += stack[-1][1]
            answer.append(stack.pop()[0])
                
    return answer

후기

반례를 찾는 게 정말 까다로운 문제였다. 인덱스만 활용한 풀이에서는 수동으로 현재 시간을 업데이트 했어야 해서 여유 시간이 생겼을 때 과거에 멈춰뒀던 과제가 없는 경우의 처리가 제대로 안 됐었다. 스택 풀이에서는 자동으로 현재 시간이 새로운 과제 시작 시간에 맞춰지도록 되어 있기 때문에 이런 에러가 없었던 것 같다.