PCCP 모의고사 2회 3번 문제 - 카페 확장

🧾 문제 설명

• 0초에 손님 한 명 도착, k초마다 새로운 손님 한 명이 줄을 섬
• 음료는 한 번에 하나씩 만듦
• 손님은 음료를 받자마자 나감
• 음료들은 0번부터 차례대로 번호가 지정되어 있음

문제 목표
주문받은 음료 목록을 이용해 손님들이 동시에 최대 몇 명이 머물렀는지 구하라.

• 주문하기까지 걸린 시간과 음료를 받고 나가는 시간은 무시
• 나감과 동시에 다른 손님이 들어올 경우, 나가는 손님이 먼저 퇴장한 후 입장

---

🔒 제한 사항

• 1 ≤ menu의 길이 ≤ 100
• menu[i]: i번 음료의 제조 시간
• 1 ≤ menu[i] ≤ 100
• 1 ≤ order의 길이 ≤ 10,000
• 0 ≤ order[i] < 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

---

💡 입출력 예 설명

예시 2

• 0초: 첫 손님 도착 → 30초에 나감
• 10초: 두 번째 손님 도착 → 42초에 나감
• 20초, 30초, 40초에 손님 도착
• → 40초~42초 사이에 4명 존재 → 최댓값 = 4

예시 3

• 입장: 0초, 5초, 10초, 15초, 20초
• 퇴장: 5초, 10초, 15초, 20초, 25초
• 입장과 퇴장이 겹치는 경우 → 퇴장이 먼저 처리됨
• → 항상 동시에 1명만 존재 → 1

---

💭 내 접근 방법

• deque에 사람의 출입 기록을 관리하고
• 최대 시간만큼 while 루프를 돌며 1초 단위로 상태를 시뮬레이션하려고 했음
• 하지만 결국 구현 실패

---

❌ 실패한 이유

• 모든 초 단위 시간을 순회하려 했기 때문에 성능 저하 발생 가능성 있음
• 입장/퇴장 시간 겹침 처리(퇴장이 우선)가 어려웠음
• deque에서 적절히 제거 & 순서 일치가 꼬이면서 논리적 오류 발생

---

✅ 정답 코드 설명 요약

• enter_times: 손님 도착 시간 리스트 (0초부터 k초 간격)
• leave_times: 음료 제조 완료 시각 = 손님 퇴장 시간
• current_time: 바리스타가 다음 음료를 만들 수 있는 시간
• 손님 i의 도착 시점에 앞선 손님들 중 아직 퇴장하지 않은 수(count) 계산
• count + 1 → 현재 손님 포함
• 이 값을 기준으로 최댓값 갱신

---

⏱ 시간복잡도 분석

• 외부 루프: O(n)
• 내부 루프: O(n) → 전체 O(n²)
• 단, n ≤ 10,000 이므로 최악 약 10⁷ 연산 → 충분히 통과 가능

---

💻 정답 코드

def solution(menu, order, k):
    """
    0초에 손님 한 명 도착, k초마다 새로운 손님 한명이 줄을 섬
    음료를 한 번에 하나씩 만듦
    손님은 음료 받자마다 나감
    음료들은 0번부터 차례대로 번호가 지정되어 있음

    주문받은 음료 목록을 이용해 손님들이 동시에 최대 몇 명이 머물렀는가
    주문하기까지 걸린 시간과 음료를 받고 나가는 시간은 무시
    나감과 동시에 다른 손님이 들어올 경우, 나가는 손님이 먼저 퇴장 후 다음 들어오는 손님이 입장
    """

    n = len(order)
    enter_times = [i * k for i in range(n)]  # 각 손님의 도착 시간
    leave_times = []  # 각 손님의 퇴장 시간

    current_time = 0  # 바리스타가 음료를 만들기 시작하는 시간

    for i in range(n):
        arrive = enter_times[i]
        make_time = menu[order[i]]

        # 바리스타가 쉬고 있는 경우
        if current_time <= arrive:
            start_time = arrive
        else:
            start_time = current_time  # 대기 후 시작

        leave_time = start_time + make_time
        leave_times.append(leave_time)
        current_time = leave_time  # 다음 음료 제조 시작 시간 갱신

    max_customers = 0

    for i in range(n):
        count = 0
        arrive_time = enter_times[i]

        for j in range(i):
            if arrive_time < leave_times[j]:
                count += 1

        max_customers = max(max_customers, count + 1)  # 현재 손님 포함

    return max_customers

---