[PCCP 모의고사#2] 카페 확장 (큐)

문제 설명

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

주원이네 카페에는 영업을 시작하자마자 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

• 본문에서 설명한 예시입니다.

입출력 예 #2

• 영업 시작 후 가장 먼저 도착한 손님은 0초에 주문을 받고 30초에 카페를 나갑니다. 영업 시작 후 10초에 도착한 손님은 42초에 음료를 받고 카페를 나가게 됩니다. 그 사이 20초, 30초, 40초에 손님들이 각각 들어와, 40초~42초 사이에 총 4명의 손님들이 동시에 카페에서 기다리고, 이 수가 동시에 기다리는 손님 수의 최댓값입니다.

풀이

• k 타임마다 order를 하나씩 처리
  • order[i] = menu의 인덱스... menu[order[i]] = 음료가 나오는 소요시간
• 이것도 우선순위큐 아니 힙큐에 손님이 도착한 시간을 넣고,
  • 소요시간이 넘어갔으면 안기다린거고, 아니면 기다린거고
    • 아? 동시에 존재한 최대 손님 수... 그러니까 max(힙큐의 길이)를 뽑는 문제...
• 근데 난 우선순위큐에 넣는 문제에 약하단 말이지...
  • 어떻게 해야돼? ㅋㅋㅋ

1트

• 그냥 배열을 하나를 더 만들고,
  • order 순서대로 도착해서 기다린 시간 + 음료 만드는데 소요된 시간을 저장하고,
    • 나중에 도착~나갈때까지의 시간이 겹치는 유저들만 찾는 방식으로 하면 안되나?
• 해보자
  • 음료 시간 [5,12,30]
  • 손님 주문 [1,2,1,1]
  • 도착 시간 [0,10,20,30] / k = 10이니까
  • 진짜 주문 [0,12,42,54...
  • 나간 시간 [12,42,54,66...
• 그럼 도착시간이랑 나간시간을 비교하면
  • (도착시간 < 나간시간)이런 케이스의 수
  • 도착 시간 [0,10,20,30]
  • 나간 시간 [12,42,54,66]
    • 2중 for문이네... 1만개x1만개... 1억개...
• 시간 얼마나 걸리나 볼까?
  • 시간 초과는 안나지만... 이건 아닌 거 같지? ㅋㅋㅋ

def solution(menu, order, k):
    answer = 0
    for i in range(len(order)):
        for j in range(len(order)):
            answer += 1
    return answer
    
확성  테스트
테스트 1 〉	실패 (969.55ms, 10MB)
테스트 2 〉	실패 (3929.77ms, 10.3MB)
테스트 3 〉	실패 (4004.79ms, 10.3MB)
테스트 4 〉	실패 (4149.90ms, 10.2MB)
테스트 5 〉	실패 (3934.17ms, 10.2MB)
테스트 6 〉	실패 (3904.80ms, 10.4MB)
테스트 7 〉	실패 (4496.92ms, 10.3MB)
테스트 8 〉	실패 (4069.37ms, 10.2MB)
테스트 9 〉	실패 (4017.02ms, 10.3MB)
테스트 10 〉	실패 (3826.11ms, 10.2MB)
테스트 11 〉	실패 (0.00ms, 10.3MB)

2트

• 힙큐 씁시다. 어떻게 해야되나... ㅠ.ㅠ
• k 타임마다
  • order를 하나씩 힙큐에 넣고... k타임을 기준으로...
  • k 타임이랑 메뉴의 소요시간만 넣으면 될 듯
    • order[i] = menu의 인덱스... menu[order[i]] = 음료가 나오는 소요시간
• 그리고 k 타임마다
  • 동시에 존재한 최대 손님 수... 그러니까 max(힙큐의 길이)를 뽑는 문제...
  • 손님이 도착한 시간 < 이전 메뉴의 소요시간이면 대기...
• 하다보니 현재 시간이 필요없네? 아닌가?
  • 이제보니 힙큐 안써도 됨.

from heapq import heappush as push, heappop as pop

def solution(menu, order, k):
    pq = []
    isWorking = False
    max_heap, i, begin, end = 0,0,0,0
    
    while len(order) > 0 or len(pq) > 0:
        
        if i % k == 0 and len(order) > 0: # 시간 될 때 마다 손님 밀어넣기
            push(pq, (i, menu[order.pop(0)]))
            print(i, pq, "손님 받기")
        
        if isWorking == True: # 일하고 있습니다. 방해하지 마세요.
            print(i,pq,"일하고 있습니다. 방해하지 마세요.")
            if end <= i:
                if len(pq) > 0:
                    a, b = pop(pq)
                isWorking = False
                print("일 끝났다", isWorking, len(pq))
        
        if isWorking == False and len(pq) > 0: # 사람이 올 시간인가?
            print("놀고 있음.")
            begin = pq[0][0]
            if begin <= i: # 올 시간이다.
                end = pq[0][1] + i
                print(i,pq,"일합니다")
                isWorking = True # 일합니다.
        
        max_heap = max(max_heap, len(pq)) # 대기중인 손님 수 비교
        i += 1
    return max_heap

테스트 1
입력값 〉	[5, 12, 30], [1, 2, 0, 1], 10
기댓값 〉	3
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	
0 [(0, 12)] 손님 받기
놀고 있음.
0 [(0, 12)] 일합니다
1 [(0, 12)] 일하고 있습니다. 방해하지 마세요.
2 [(0, 12)] 일하고 있습니다. 방해하지 마세요.
3 [(0, 12)] 일하고 있습니다. 방해하지 마세요.
4 [(0, 12)] 일하고 있습니다. 방해하지 마세요.
5 [(0, 12)] 일하고 있습니다. 방해하지 마세요.
6 [(0, 12)] 일하고 있습니다. 방해하지 마세요.
7 [(0, 12)] 일하고 있습니다. 방해하지 마세요.
8 [(0, 12)] 일하고 있습니다. 방해하지 마세요.
9 [(0, 12)] 일하고 있습니다. 방해하지 마세요.
10 [(0, 12), (10, 30)] 손님 받기
10 [(0, 12), (10, 30)] 일하고 있습니다. 방해하지 마세요.
11 [(0, 12), (10, 30)] 일하고 있습니다. 방해하지 마세요.
12 [(0, 12), (10, 30)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 1
놀고 있음.
12 [(10, 30)] 일합니다
13 [(10, 30)] 일하고 있습니다. 방해하지 마세요.
14 [(10, 30)] 일하고 있습니다. 방해하지 마세요.
15 [(10, 30)] 일하고 있습니다. 방해하지 마세요.
16 [(10, 30)] 일하고 있습니다. 방해하지 마세요.
17 [(10, 30)] 일하고 있습니다. 방해하지 마세요.
18 [(10, 30)] 일하고 있습니다. 방해하지 마세요.
19 [(10, 30)] 일하고 있습니다. 방해하지 마세요.
20 [(10, 30), (20, 5)] 손님 받기
20 [(10, 30), (20, 5)] 일하고 있습니다. 방해하지 마세요.
21 [(10, 30), (20, 5)] 일하고 있습니다. 방해하지 마세요.
22 [(10, 30), (20, 5)] 일하고 있습니다. 방해하지 마세요.
23 [(10, 30), (20, 5)] 일하고 있습니다. 방해하지 마세요.
24 [(10, 30), (20, 5)] 일하고 있습니다. 방해하지 마세요.
25 [(10, 30), (20, 5)] 일하고 있습니다. 방해하지 마세요.
26 [(10, 30), (20, 5)] 일하고 있습니다. 방해하지 마세요.
27 [(10, 30), (20, 5)] 일하고 있습니다. 방해하지 마세요.
28 [(10, 30), (20, 5)] 일하고 있습니다. 방해하지 마세요.
29 [(10, 30), (20, 5)] 일하고 있습니다. 방해하지 마세요.
30 [(10, 30), (20, 5), (30, 12)] 손님 받기
30 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
31 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
32 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
33 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
34 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
35 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
36 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
37 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
38 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
39 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
40 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
41 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
42 [(10, 30), (20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 2
놀고 있음.
42 [(20, 5), (30, 12)] 일합니다
43 [(20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
44 [(20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
45 [(20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
46 [(20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
47 [(20, 5), (30, 12)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 1
놀고 있음.
47 [(30, 12)] 일합니다
48 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
49 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
50 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
51 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
52 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
53 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
54 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
55 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
56 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
57 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
58 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
59 [(30, 12)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 0

테스트 2
입력값 〉	[5, 12, 30], [2, 1, 0, 0, 0, 1, 0], 10
기댓값 〉	4
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	
0 [(0, 30)] 손님 받기
놀고 있음.
0 [(0, 30)] 일합니다
1 [(0, 30)] 일하고 있습니다. 방해하지 마세요.
2 [(0, 30)] 일하고 있습니다. 방해하지 마세요.
3 [(0, 30)] 일하고 있습니다. 방해하지 마세요.
4 [(0, 30)] 일하고 있습니다. 방해하지 마세요.
5 [(0, 30)] 일하고 있습니다. 방해하지 마세요.
6 [(0, 30)] 일하고 있습니다. 방해하지 마세요.
7 [(0, 30)] 일하고 있습니다. 방해하지 마세요.
8 [(0, 30)] 일하고 있습니다. 방해하지 마세요.
9 [(0, 30)] 일하고 있습니다. 방해하지 마세요.
10 [(0, 30), (10, 12)] 손님 받기
10 [(0, 30), (10, 12)] 일하고 있습니다. 방해하지 마세요.
11 [(0, 30), (10, 12)] 일하고 있습니다. 방해하지 마세요.
12 [(0, 30), (10, 12)] 일하고 있습니다. 방해하지 마세요.
13 [(0, 30), (10, 12)] 일하고 있습니다. 방해하지 마세요.
14 [(0, 30), (10, 12)] 일하고 있습니다. 방해하지 마세요.
15 [(0, 30), (10, 12)] 일하고 있습니다. 방해하지 마세요.
16 [(0, 30), (10, 12)] 일하고 있습니다. 방해하지 마세요.
17 [(0, 30), (10, 12)] 일하고 있습니다. 방해하지 마세요.
18 [(0, 30), (10, 12)] 일하고 있습니다. 방해하지 마세요.
19 [(0, 30), (10, 12)] 일하고 있습니다. 방해하지 마세요.
20 [(0, 30), (10, 12), (20, 5)] 손님 받기
20 [(0, 30), (10, 12), (20, 5)] 일하고 있습니다. 방해하지 마세요.
21 [(0, 30), (10, 12), (20, 5)] 일하고 있습니다. 방해하지 마세요.
22 [(0, 30), (10, 12), (20, 5)] 일하고 있습니다. 방해하지 마세요.
23 [(0, 30), (10, 12), (20, 5)] 일하고 있습니다. 방해하지 마세요.
24 [(0, 30), (10, 12), (20, 5)] 일하고 있습니다. 방해하지 마세요.
25 [(0, 30), (10, 12), (20, 5)] 일하고 있습니다. 방해하지 마세요.
26 [(0, 30), (10, 12), (20, 5)] 일하고 있습니다. 방해하지 마세요.
27 [(0, 30), (10, 12), (20, 5)] 일하고 있습니다. 방해하지 마세요.
28 [(0, 30), (10, 12), (20, 5)] 일하고 있습니다. 방해하지 마세요.
29 [(0, 30), (10, 12), (20, 5)] 일하고 있습니다. 방해하지 마세요.
30 [(0, 30), (10, 12), (20, 5), (30, 5)] 손님 받기
30 [(0, 30), (10, 12), (20, 5), (30, 5)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 3
놀고 있음.
30 [(10, 12), (30, 5), (20, 5)] 일합니다
31 [(10, 12), (30, 5), (20, 5)] 일하고 있습니다. 방해하지 마세요.
32 [(10, 12), (30, 5), (20, 5)] 일하고 있습니다. 방해하지 마세요.
33 [(10, 12), (30, 5), (20, 5)] 일하고 있습니다. 방해하지 마세요.
34 [(10, 12), (30, 5), (20, 5)] 일하고 있습니다. 방해하지 마세요.
35 [(10, 12), (30, 5), (20, 5)] 일하고 있습니다. 방해하지 마세요.
36 [(10, 12), (30, 5), (20, 5)] 일하고 있습니다. 방해하지 마세요.
37 [(10, 12), (30, 5), (20, 5)] 일하고 있습니다. 방해하지 마세요.
38 [(10, 12), (30, 5), (20, 5)] 일하고 있습니다. 방해하지 마세요.
39 [(10, 12), (30, 5), (20, 5)] 일하고 있습니다. 방해하지 마세요.
40 [(10, 12), (30, 5), (20, 5), (40, 5)] 손님 받기
40 [(10, 12), (30, 5), (20, 5), (40, 5)] 일하고 있습니다. 방해하지 마세요.
41 [(10, 12), (30, 5), (20, 5), (40, 5)] 일하고 있습니다. 방해하지 마세요.
42 [(10, 12), (30, 5), (20, 5), (40, 5)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 3
놀고 있음.
42 [(20, 5), (30, 5), (40, 5)] 일합니다
43 [(20, 5), (30, 5), (40, 5)] 일하고 있습니다. 방해하지 마세요.
44 [(20, 5), (30, 5), (40, 5)] 일하고 있습니다. 방해하지 마세요.
45 [(20, 5), (30, 5), (40, 5)] 일하고 있습니다. 방해하지 마세요.
46 [(20, 5), (30, 5), (40, 5)] 일하고 있습니다. 방해하지 마세요.
47 [(20, 5), (30, 5), (40, 5)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 2
놀고 있음.
47 [(30, 5), (40, 5)] 일합니다
48 [(30, 5), (40, 5)] 일하고 있습니다. 방해하지 마세요.
49 [(30, 5), (40, 5)] 일하고 있습니다. 방해하지 마세요.
50 [(30, 5), (40, 5), (50, 12)] 손님 받기
50 [(30, 5), (40, 5), (50, 12)] 일하고 있습니다. 방해하지 마세요.
51 [(30, 5), (40, 5), (50, 12)] 일하고 있습니다. 방해하지 마세요.
52 [(30, 5), (40, 5), (50, 12)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 2
놀고 있음.
52 [(40, 5), (50, 12)] 일합니다
53 [(40, 5), (50, 12)] 일하고 있습니다. 방해하지 마세요.
54 [(40, 5), (50, 12)] 일하고 있습니다. 방해하지 마세요.
55 [(40, 5), (50, 12)] 일하고 있습니다. 방해하지 마세요.
56 [(40, 5), (50, 12)] 일하고 있습니다. 방해하지 마세요.
57 [(40, 5), (50, 12)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 1
놀고 있음.
57 [(50, 12)] 일합니다
58 [(50, 12)] 일하고 있습니다. 방해하지 마세요.
59 [(50, 12)] 일하고 있습니다. 방해하지 마세요.
60 [(50, 12), (60, 5)] 손님 받기
60 [(50, 12), (60, 5)] 일하고 있습니다. 방해하지 마세요.
61 [(50, 12), (60, 5)] 일하고 있습니다. 방해하지 마세요.
62 [(50, 12), (60, 5)] 일하고 있습니다. 방해하지 마세요.
63 [(50, 12), (60, 5)] 일하고 있습니다. 방해하지 마세요.
64 [(50, 12), (60, 5)] 일하고 있습니다. 방해하지 마세요.
65 [(50, 12), (60, 5)] 일하고 있습니다. 방해하지 마세요.
66 [(50, 12), (60, 5)] 일하고 있습니다. 방해하지 마세요.
67 [(50, 12), (60, 5)] 일하고 있습니다. 방해하지 마세요.
68 [(50, 12), (60, 5)] 일하고 있습니다. 방해하지 마세요.
69 [(50, 12), (60, 5)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 1
놀고 있음.
69 [(60, 5)] 일합니다
70 [(60, 5)] 일하고 있습니다. 방해하지 마세요.
71 [(60, 5)] 일하고 있습니다. 방해하지 마세요.
72 [(60, 5)] 일하고 있습니다. 방해하지 마세요.
73 [(60, 5)] 일하고 있습니다. 방해하지 마세요.
74 [(60, 5)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 0

테스트 3
입력값 〉	[5], [0, 0, 0, 0, 0], 5
기댓값 〉	1
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	
0 [(0, 5)] 손님 받기
놀고 있음.
0 [(0, 5)] 일합니다
1 [(0, 5)] 일하고 있습니다. 방해하지 마세요.
2 [(0, 5)] 일하고 있습니다. 방해하지 마세요.
3 [(0, 5)] 일하고 있습니다. 방해하지 마세요.
4 [(0, 5)] 일하고 있습니다. 방해하지 마세요.
5 [(0, 5), (5, 5)] 손님 받기
5 [(0, 5), (5, 5)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 1
놀고 있음.
5 [(5, 5)] 일합니다
6 [(5, 5)] 일하고 있습니다. 방해하지 마세요.
7 [(5, 5)] 일하고 있습니다. 방해하지 마세요.
8 [(5, 5)] 일하고 있습니다. 방해하지 마세요.
9 [(5, 5)] 일하고 있습니다. 방해하지 마세요.
10 [(5, 5), (10, 5)] 손님 받기
10 [(5, 5), (10, 5)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 1
놀고 있음.
10 [(10, 5)] 일합니다
11 [(10, 5)] 일하고 있습니다. 방해하지 마세요.
12 [(10, 5)] 일하고 있습니다. 방해하지 마세요.
13 [(10, 5)] 일하고 있습니다. 방해하지 마세요.
14 [(10, 5)] 일하고 있습니다. 방해하지 마세요.
15 [(10, 5), (15, 5)] 손님 받기
15 [(10, 5), (15, 5)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 1
놀고 있음.
15 [(15, 5)] 일합니다
16 [(15, 5)] 일하고 있습니다. 방해하지 마세요.
17 [(15, 5)] 일하고 있습니다. 방해하지 마세요.
18 [(15, 5)] 일하고 있습니다. 방해하지 마세요.
19 [(15, 5)] 일하고 있습니다. 방해하지 마세요.
20 [(15, 5), (20, 5)] 손님 받기
20 [(15, 5), (20, 5)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 1
놀고 있음.
20 [(20, 5)] 일합니다
21 [(20, 5)] 일하고 있습니다. 방해하지 마세요.
22 [(20, 5)] 일하고 있습니다. 방해하지 마세요.
23 [(20, 5)] 일하고 있습니다. 방해하지 마세요.
24 [(20, 5)] 일하고 있습니다. 방해하지 마세요.
25 [(20, 5)] 일하고 있습니다. 방해하지 마세요.
일 끝났다 False 0

• 제출 코드
  • heapq, push, pop을 안써도 되지 않았나 싶은 문제
  • order.pop(0)을 안해도 되고, heapq가 아니라 그냥 큐로도 되는 문제 같다.

from heapq import heappush as push, heappop as pop

def solution(menu, order, k):
    pq = []
    isWorking = False
    max_heap, i, begin, end = 0,0,0,0
    
    while len(order) > 0 or len(pq) > 0:
        if i % k == 0 and len(order) > 0: # 시간 될 때 마다 손님 밀어넣기
            push(pq, (i, menu[order.pop(0)]))
        if isWorking == True: # 일하고 있습니다. 방해하지 마세요.
            if end <= i:
                if len(pq) > 0:
                    a, b = pop(pq)
                isWorking = False
        if isWorking == False and len(pq) > 0: # 사람이 올 시간인가?
            begin = pq[0][0]
            if begin <= i: # 올 시간이다.
                end = pq[0][1] + i
                isWorking = True # 일합니다.
        max_heap = max(max_heap, len(pq)) # 대기중인 손님 수 비교
        i += 1
    
    return max_heap

정확성  테스트
테스트 1 〉	통과 (129.21ms, 10.5MB)
테스트 2 〉	통과 (272.53ms, 10.4MB)
테스트 3 〉	통과 (222.08ms, 10.5MB)
테스트 4 〉	통과 (175.08ms, 10.2MB)
테스트 5 〉	통과 (260.12ms, 10.3MB)
테스트 6 〉	통과 (416.68ms, 10.8MB)
테스트 7 〉	통과 (294.51ms, 10.4MB)
테스트 8 〉	통과 (201.26ms, 10.5MB)
테스트 9 〉	통과 (303.49ms, 10.5MB)
테스트 10 〉	통과 (266.56ms, 10.4MB)
테스트 11 〉	통과 (0.03ms, 10.4MB)

• 고수의 풀이

from collections import deque

def solution(menu, order, k):
    queue = deque()
    busy = -1 
    idx = answer = 0

    for t in range(k * (len(order) - 1) + 1):
        if k * idx == t:
            queue.append(order[idx])
            idx += 1

        if busy == t:
            queue.popleft()
            busy = -1

        if busy == -1 and len(queue) > 0:
            busy = t + menu[queue[0]]

        answer = max(answer, len(queue))

    return answer

정확성  테스트
테스트 1 〉	통과 (37.77ms, 10.2MB)
테스트 2 〉	통과 (121.48ms, 10.3MB)
테스트 3 〉	통과 (143.25ms, 10.3MB)
테스트 4 〉	통과 (147.11ms, 10.3MB)
테스트 5 〉	통과 (163.29ms, 10.4MB)
테스트 6 〉	통과 (100.23ms, 10.3MB)
테스트 7 〉	통과 (160.65ms, 10.2MB)
테스트 8 〉	통과 (102.88ms, 10.3MB)
테스트 9 〉	통과 (125.74ms, 10.3MB)
테스트 10 〉	통과 (133.00ms, 10.4MB)
테스트 11 〉	통과 (0.01ms, 10.1MB)

• 더 고수의 풀이

from collections import deque

def solution(menu, order, k):
    answer = 1

    enter = deque([x * k for x in range(len(order))])
    q = deque([enter.popleft()])
    curr = 0
    for i in range(len(order)):
        curr = max(curr, i * k) + menu[order[i]]
        while enter and enter[0] < curr:
            q.append(enter.popleft())

        answer = max(answer, len(q))
        q.popleft()

        if enter and enter[0] == curr:
            q.append(enter.popleft())

    return answer

정확성  테스트
테스트 1 〉	통과 (3.36ms, 10.4MB)
테스트 2 〉	통과 (6.65ms, 10.5MB)
테스트 3 〉	통과 (7.97ms, 10.5MB)
테스트 4 〉	통과 (6.76ms, 10.5MB)
테스트 5 〉	통과 (11.85ms, 10.6MB)
테스트 6 〉	통과 (6.32ms, 10.6MB)
테스트 7 〉	통과 (13.66ms, 10.6MB)
테스트 8 〉	통과 (8.34ms, 10.3MB)
테스트 9 〉	통과 (6.42ms, 10.3MB)
테스트 10 〉	통과 (6.76ms, 10.6MB)
테스트 11 〉	통과 (0.02ms, 10.2MB)