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

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

프로그래머스

 

✍️ 문제 요약

- `plans`는 시간 순으로 정렬되어 있지 않을 수 있다.

- 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작한다.

 

🤔 접근법

`done`: 완료한 순서대로 과제 이름을 저장할 리스트

`stack`: 완료하지 못하고 멈춘 과제를 담아둘 리스트

 

`plans`를 순회하며 각각의 과제에 대해 아래처럼 분기한다.

 

- 과제를 완료하지 못한 경우 (`start + playtime`이 다음 과제의 시작 시간보다 큰 경우)

    - 잔여 시간(`playtime`)을 갱신하여 대기열(`stack`)에 추가

- 과제를 완료한 경우 (`start + playtime`이 다음 과제의 시작 시간보다 작거나 같은 경우)

    - `done`에 추가한다.

    - 다음 과제 시작 전까지 시간이 남는 경우

        - 대기열(`stack`)에 가장 최근에 저장된 과제를 진행

            - 대기열 과제를 완료한 경우 `done`에 추가

            - 대기열 과제를 완료하지 못한 경우 잔여 시간(`playtime`)을 갱신하여 대기열(`stack`)에 추가

- 가장 마지막에 진행하는 과제는 무조건 `done`에 추가

- `plans`를 모두 순회하고 대기열(`stack`)에 남아있는 과제는, `pop()`하여 마지막 원소부터 `done`에 추가

 

💪 무식하게 풀기

아래는 정확성이 낮은 코드이다. 그 아래 정확성을 높인 코드에서 세부 로직을 설명하겠다.

def hourToMin(str):
    hh, mm = map(int, str.split(':'))
    return hh * 60 + mm

def solution(plans):
    done = [] # 완료한 과제
    stack = [] # 멈춘 과제 리스트 (가장 최근부터 다시 한다)
    
    plans.sort(key=lambda x:x[1])
    
    now = 0 # 현재 시각
    for i in range(len(plans)-1):
        cur_nm, cur_st, cur_pt = plans[i][0], hourToMin(plans[i][1]), int(plans[i][2])
        next_st = hourToMin(plans[i+1][1])
        
        if cur_st + cur_pt > next_st: # 다 못 끝내고 대기열에 넣어야 한다
            stack.append([cur_nm, cur_st + cur_pt - next_st]) # 튜플은 변경 못함
            now = next_st
        elif cur_st + cur_pt == next_st: # 다 끝낼 수 있지만 대기열에 있는 과제는 못한다
            done.append(cur_nm)
            now = next_st
        else: # 다 끝내고 대기열에 있는 과제도 잠깐 한다
            done.append(cur_nm)
            now = cur_st + cur_pt
            while stack:
                if now + stack[-1][1] <= next_st: # 다 할 수 있다
                    done.append(stack.pop()[0]) # 과제 이름만 append
                else: # 일부만 한다 -> 대기열 과제 남은 시간 갱신
                    stack[-1][1] = now + stack[-1][1] - next_st
                    break
    
    # 맨 마지막 과목
    done.append(plans[-1][0])
    
    # 대기열에서 하나씩 뽑아서 정답 리스트에 이어붙인다.
    while stack:
        done.append(stack.pop()[0]) # 과제 이름만 append
    
    return done

정확성: 75.0

 

🎯 정확성 높이기

전체 코드

def hourToMin(str):
    hh, mm = map(int, str.split(':'))
    return hh * 60 + mm

def solution(plans):
    done = [] # 완료한 과제
    stack = [] # 멈춘 과제 리스트 (가장 최근부터 다시 한다)
    
    plans.sort(key=lambda x:x[1])
    
    for i in range(len(plans)):
        if i == len(plans) - 1: # 맨 마지막 과제는 무조건 한다
        done.append(plans[i][0])
            break
            
        name, start, pt = plans[i][0], hourToMin(plans[i][1]), int(plans[i][2])
        nStart = hourToMin(plans[i+1][1]) # 다음 과제 시작 시간
        
        if start + pt > nStart: # 다 못 끝내고 대기열에 넣어야 한다
            stack.append([name, (start+pt)-nStart]) # 튜플은 변경 못함
        else: # 다 끝낼 수 있다
            done.append(name)
            remaining = nStart - (start + pt) # 다음 과제 시작 전까지 남은 시간
            
            while remaining != 0 and stack: # 다 끝내고 대기열에 있는 과제도 잠깐 한다
                nn, pp = stack.pop() # 대기열에 있는 name, playtime
                if remaining >= pp: # 대기열 과제를 마칠 수 있는 경우
                    done.append(nn)
                    remaining -= pp
                else: # 일부만 하고 다시 대기열에 넣는다
                    stack.append([nn, pp - remaining])
                    remaining = 0
    
    # 대기열에서 순서대로 pop하여 done 리스트에 추가
    while stack:
        done.append(stack.pop()[0]) # 과제 이름만 append
    
    return done

정확성 100.0

 

세부 설명

우선, `plans` 리스트는 정렬되어 있지 않기 때문에 `과제 시작 시간`을 기준으로 오름차순 정렬을 해야 한다.

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

 

이제 `plans`를 순회하면서, 위에서 언급한 분기 처리를 해야 한다.

우선, 맨 마지막 과제는 다음 과제가 없기 때문에 무조건 끝마칠 수 있다.

따라서 맨 마지막 과제는 `done` 리스트에 넣고 반복문을 종료하면 된다.

for i in range(len(plans)):
    if i == len(plans) - 1: # 맨 마지막 과제는 무조건 한다
    done.append(plans[i][0])
        break

 

`plans`의 원소는 `[name, start, playtime]`의 구조로 이루어져 있다. 예를 들면, `["korean", "11:40", "30"]`의 형태이다.

이때 start는 "분" 형태로 변경하고, playtime은 기존 문자열에서 정수형으로 변경해야 계산할 수 있다.

 

과제를 마칠 수 있는지 계산하기 위해 다음 과제의 시작시간(`nStart`)도 필요하다.

name, start, pt = plans[i][0], hourToMin(plans[i][1]), int(plans[i][2])
nStart = hourToMin(plans[i+1][1]) # 다음 과제 시작 시간
...
def hourToMin(str):
    hh, mm = map(int, str.split(':'))
    return hh * 60 + mm

 

과제를 마칠 수 없다면, 할 수 있는 만큼만 하고 `playtime`을 갱신한 뒤 대기열(`stack`)에 추가한다.

이때 튜플이 아니라 리스트 형태로 저장하는 이유는, 나중에 대기열에 있는 과제들의 `playtime`을 갱신해야 하기 때문이다.

if start + pt > nStart: # 다 못 끝내고 대기열에 넣어야 한다
    stack.append([name, (start+pt)-nStart])

 

과제를 마칠 수 있다면 두 가지 경우의 수가 존재한다.

1) 현재 과제만 마칠 수 있는 경우

2) 현재 과제를 마치고 다음 과제 시작 전까지 대기열의 과제를 손댈 수 있는 경우

 

위 두가지 경우를 판단하기 위해 다음 과제 시작 전까지 남은 시간(`remaining`)을 계산한다.

남은 시간이 있으면서 대기열(`stack`)에 과제가 있다면, 2번의 경우로 대기열의 과제까지 (할 수 있는 만큼) 한다.

else: # 과제를 마칠 수 있는 경우
    done.append(name)
    remaining = nStart - (start + pt) # 다음 과제 시작 전까지 남은 시간

    while remaining != 0 and stack: # 다 끝내고 대기열에 있는 과제도 잠깐 한다
        nn, pp = stack.pop() # 대기열에 있는 name, playtime
        if remaining >= pp: # 대기열 과제를 마칠 수 있는 경우
            done.append(nn)
            remaining -= pp
        else: # 일부만 하고 다시 대기열에 넣는다
            stack.append([nn, pp - remaining])
            remaining = 0

 

마지막으로, `plans` 순회를 마쳤다면 대기열에 남은 과제를 순서대로 `pop()`하여 끝내면 된다.

# 대기열에서 순서대로 pop하여 done 리스트에 추가
while stack:
    done.append(stack.pop()[0]) # 과제 이름만 append

 

👀 다른 사람의 코드를 탐구해보기

전체 코드

def hourToMin(str):
    hh, mm = map(int, str.split(':'))
    return hh * 60 + mm

def solution(plans):
    # plans = sorted(map(lambda x: [x[0], hourToMin(x[1]), int(x[2])], plans), key=lambda x: -x[1])
    plans = map(lambda x: [x[0], hourToMin(x[1]), int(x[2])], plans)
    plans = sorted(plans, key=lambda x: x[1], reverse=True)
    
    done = []
    while plans:
        name, start, playtime = plans.pop()
        for i, x in enumerate(done):
            if x[0] > start:
                done[i][0] += playtime
        done.append([start + playtime, name]) # [과제를 마친 시각, 이름]
    done.sort()

    return list(map(lambda x: x[1], done))

 

세부 설명

가장 핵심은 아래 코드이다.

- `x`: 이미 완료된 과제들 중 하나

- `x[0]`: 해당 이전 과제가 끝난 시간

- `start`: 현재 처리 중인 과제의 시작 시간

- `playtime`: 현재 처리 중인 과제의 소요 시간

 

따라서 `if x[0] > start:`는 현재 처리 중인 과제의 시작 시간(`start`)와 이전에 완료된 과제(`x`)의 끝난 시간(`x[0]`)을 비교한다.

만약, `x[0]`이 `start`보다 크다면, 이전에 완료된 과제 `x`와 현재 처리 중인 과제가 중첩되는 경우다.

 

중첩된 경우에는 이전 과제의 끝난 시간(`done[i][0]`)을 업데이트 하여 현재 처리 중인 과제가 끝난 이후로 시간을 더해준다.

for i, x in enumerate(done):
    if x[0] > start:
        done[i][0] += playtime

 

📚 참고 자료

https://velog.io/@yeomja99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B3%BC%EC%A0%9C-%EC%A7%84%ED%96%89%ED%95%98%EA%B8%B0