문제 설명

주원이는 카페를 운영하고 있습니다. 주원이의 카페는 맛집으로 소문나서 항상 줄이 끊이지 않습니다. 
하지만 카페가 협소하여 커피를 기다리는 손님들은 종종 불만을 토로하고 있습니다. 
주원이는 카페를 확장하기로 하고, 얼마나 많은 손님들이 동시에 카페에 머무는지 확인해보려 합니다.

주원이네 카페에는 영업을 시작하자마자 0초에 손님 한 명이 가게에 도착하고, 정확히 k초마다 새로운 손님 한 명이 카페에 와서 줄을 섭니다. 
손님들은 키오스크를 통해 주문하고, 주원이는 주문받은 순서대로 음료를 만듭니다. 주원이는 음료를 한 번에 하나씩 만들며, 
지금 만들고 있는 음료를 다 만들면 다음 음료를 만들기 시작합니다. 손님은 자신이 주문한 음료를 받자마자 카페를 나갑니다. 
주원이네 카페에는 여러 종류의 음료를 판매하고 있는데 각 음료들은 0번부터 차례대로 번호가 지정되어 있습니다. 
또한 주원이가 같은 종류의 음료를 만드는데 걸리는 시간은 항상 동일합니다.

주원이는 오늘 주문받은 음료 목록을 이용하여, 카페에서 손님들이 동시에 최대 몇 명이 머물렀는지 알고 싶습니다. 
손님들이 카페에 도착하여 주문하기까지 걸린 시간과 음료를 받은 후 카페를 나가는 시간은 음료 제조 시간에 비해 대단히 짧기 때문에 무시합니다. 
한 손님이 카페에서 나감과 동시에 다른 손님이 카페에 들어올 경우, 나가는 손님이 먼저 퇴장한 다음 들어오는 손님이 입장합니다.

예를 들어, 주원이네 카페에서 세 종류의 음료를 판매하고 제조 시간은 0번 음료가 5초, 1번 음료가 12초, 2번 음료는 30초 소요된다고 가정합니다. 
영업을 시작한 뒤 4명의 손님이 각각 0초, 10초, 20초, 30초에 카페에 도착하여 순서대로 1번, 2번, 0번, 1번 음료를 주문한 경우, 
영업 시작 후 30초부터 42초 사이에 3명의 손님이 기다리게 되고, 이때가 동시에 기다리고 있는 손님이 가장 많은 시간입니다.

주원이네 카페에서 판매하는 각 음료들의 제조 시간을 담은 정수 배열 menu와 오늘 손님들이 주문한 음료가 순서대로 적힌 배열 order, 
새로운 한 명의 손님이 방문하는데 걸리는 시간인 k가 매개변수로 주어집니다. 
오늘 카페에 동시에 존재한 손님 수의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

1 ≤ menu의 길이 ≤ 100   
	menu[i]는 i번 음료의 제조 시간을 의미합니다.
	1 ≤ menu의 원소 ≤ 100
1 ≤ order의 길이 ≤ 10,000
	order[i]는 i번째 손님이 주문한 음료의 번호입니다.
	0 ≤ order의 원소 < menu의 길이
1 ≤ k ≤ 100

입출력 예

menu	order	k	result
[5, 12, 30]	[1, 2, 0, 1]	10	3
[5, 12, 30]	[2, 1, 0, 0, 0, 1, 0]	10	4
[5]	[0, 0, 0, 0, 0]	5	1
입출력 예 설명
입출력 예 #1

나의 풀이

def solution(menu, order, k):
    order_list = []
    current = []

    for i in range(len(order)):
        # 1회 반복에 1회 주문 리스트 추가
        order_list.append(menu[order[i]])

        # 현재의 주문 수 리스트에 추가
        current.append(len(order_list))

        # 제일 앞 손님 음료 제조 시간 차감
        order_list[0] = order_list[0] - k

        # 차감 결과가 음수라면 바로 다음 주문의 제조 시간 차감
        # 음수가 된 주문 리스트에서 제거하여 다음 손님이 제일 앞 손님이 됨
        while order_list and order_list[0] <= 0:
            if len(order_list) >= 2:
                order_list[1] += order_list[0]
            order_list.pop(0)

    # 주문 수 목록에서 제일 큰 수 리턴
    return max(current)          

나의 풀이 해설

1. order_list에 order 값을 차례로 넣어준다.

   order_list.append(menu[order[i]])

2. current에 현재 order_list의 길이를 저장해준다.

   order_list[1] = order_list[0] + order_list[1]

3. 맨 앞 주문 (order_list[0]) 의 시간(k)을 차감한다.

   order_list[0] = order_list[0] - k

4. 차감 후 order_list[0] 의 값이 0 이거나 음수 값이 되었다면

   현재 order_list 길이가 2 이상일때

   음수 또는 0 이 된 맨 앞 주문 (order_list[0]) 과
   바로 다음 주문 (order_list[1]) 의 값을 더해서 order_list[1]에 저장한다.

   order_list[1] = order_list[0] + order_list[1]

   그후 맨 앞 주문 (order_list[0])을 제거하여 order_list[1]이 맨 앞 주문이 되게한다.

   order_list.pop(0)

   이 반복은 맨 앞 주문이 1이상일때까지 반복된다.

   order_list 길이가 1이하라면 그냥 order_list.pop(0)을 수행한다
   (대기시간보다 짧은 주문이면서, 다음주문이 없기때문)

5. current에 저장된 주문 수 중 가장 큰값을 반환한다.

   return max(current)  

시행착오 #1

def solution(menu, order, k):
    
    order_list = []
    current = []
    
    for i in range(len(order)):
        order_list.append(menu[order[i]])
        
        if order_list[0] > 0:
            order_list[0] = order_list[0] - k
            if order_list[0] == 0 :
                order_list.pop(0)
            
            current.append(len(order_list))
            
        elif order_list[0] < 0:
            order_list[1] = order_list[1] + order_list[0]
            order_list.pop(0)

            current.append(len(order_list))
                
        elif order_list[0] == 0 :
            order_list.pop(0)
                
    return max(current)

1. order_list[0] 가 양수일때와 음수일때 두가지 조건을 나누었다.

   그러다보니 1회반복에 모든 절차가 실행되지않고
   1회 반복에 무조건 k를 차감하고 차감후 조건을 판단하여 order_list[0]이 음수라면 양수가 될때까지 반복하도록 하였다.

2. current의 저장 위치를 모든 절차가 진행되고 추가하였다.

   최대 대기손님수인 상태에서 절차가 수행되어 주문이 하나가 완료되서
   1이 모자란 경우가 발생했다.
   order 값이 추가된 직후에 current 값이 추가되도록 하였다.

3. 1회 반복에 음수 처리를 한번만 해주었다.

   첫주문이 음수가 된 경우 다음주문 시간을 그만큼 차감하여 처리하였는데.
   차감한 다음주문의 시간이 음수로 남아있는 경우가 발생.
   if문을 while문으로 변경하여 order_list[0]이 양수가 될때까지 반복처리하였다.

위의 문제점들을 가지고도 2개의 테스트가 통과되었다...
진짜 거의다온거 같아서 꺾이지 않는 마음으로 도전하였다...

시행착오 #2

def solution(menu, order, k):
    
    order_list = []
    current = []
    
    for i in range(len(order)):
        order_list.append(menu[order[i]])
        current.append(len(order_list))
        
        order_list[0] = order_list[0] - k 
        
        while order_list[0] < 0:
            order_list[0] + order_list[1]
            order_list.pop(0)
            
        if order_list[0] == 0: 
            order_list.pop(0)
            
    return max(current)

시행착오 #1의 문제점들을 모두 개선하여 제시된 3개의 테스트 케이스는 통과했다.
기쁜마음에 제출을 눌렀지만 제출 결과가 모조리 실패했다....

1. order_list의 길이가 1이하일때 order_list[0] + order_list[1] 를 할 수 없는걸 고려하지 않았다.

   if len(order_list) >= 2: 조건절을 추가하여 order_list의 길이가 2 이상일때만 두 요소를 더하도록 하였다

2. 1번의 문제를 수정하고 나니 ==0일때 조건을 while문 안에 넣어 시간복잡도를 감소시킬 수 있었다.

   while order_list[0] <= 0: 로 조건을 수정해서 0일때는 무조건 pop(0) 되도록하였다

..