[프로그래머스 PCCP 모의고사 3번] 카페 확장

from collections import deque
def solution(menu, order, k):
    answer = 0
    queue = deque()
    for i in order:
        queue.append(menu[i])

        answer = max(answer,len(queue))

        time = k

        while queue:
            # queue[0]과 time을 비교(걸리는 시간과 남은 시간)
            if queue[0] < time:
                time -= queue[0]
                queue.popleft()
            elif queue[0] > time:
                queue[0] -= time
                break
            else:
                queue.popleft()
                break

    return answer

 

이번 문제는 Queue 자료구조를 사용하여 푸는 문제인데 문제의 조건이 조금 복잡하다.(구현 문제에 가까움) 문제의 조건은 다음과 같다.

1. '영업을 시작할 때'와 'k초 마다' 새로운 손님이 방문하고 줄을 서게 된다.
2. 주문받은 순서대로 음료를 만들고, 다 만들고 나면 맨 앞의 손님이 퇴장한다.
3. 병렬적으로 음료를 만드는 것이 아니라, 현재 음료를 다 만들어야 다음 음료를 만들기 시작한다.

처음에는 time을 하나씩 +1 해가면서 구현하였는데, 몇몇 테스트케이스에서 틀리게 되어 강사님의 풀이를 참고하였다.

 

결국 현재 카페에서 줄을 서고 있는 사람들을 담고 있는 Queue는 k번째에만 추가가 되고 pop되는 과정이 반복되기 때문에, k번째에서만 최대 길이를 계산해줘도 된다는 것이 핵심이다.

 

먼저 주문한 음료에 대한 시간(queue.append(menu[i]))을 추가해준 뒤, while문을 돌면서 k 시간 내에 제작이 가능하다면 queue에서 pop 시켜줌과 동시에 남은 시간(time)을 갱신시켜준다.

 

근데 만약에 주어진 k 시간 내에 제작하지 못하면 queue를 pop시키지 않고 남은 제작시간을 남겨준 채 다음 주문을 받는다.(10초 내에 12초가 걸리는 음료를 제작하지 못한다면 다음 k 시간에 2초 간 제작을 해야 함)

 

이런식으로 Queue를 유지해주는 방법으로 최대 길이를 구하는 문제였다. 앞으로 이런 문제가 나오면 단순히 하나씩 계산하는 것보다 정해진 주기를 체크해주는 방법도 고려해보아야겠다고 느꼈다.