[Programmers] PCCP 모의고사#2 3번-카페 확장

 

https://school.programmers.co.kr/learn/courses/15009/lessons/121689

프로그래머스

 

테케는 맞으나, 제출 돌렸을떄 시간초과를 해결 못했다

# 0초에 한명, k초마다 새로운 손님 한 명 
# 주문 순서대로, 한 번에 하나씩 만듬
# 카페에서 손님들이 동시에 최대 몇 명 머물렀는지?
# menu : 제조시간 / order : 주문한 음료 번호 / k 방문 간격

# 아이디어 : 10초마다 현재 몇 명 있는지 세서 최댓값 업데이트
# 다 만들면 다음음료 만들 수 있으니까 deque

from collections import deque

def solution(menu, order, k):
    answer = -1e9
    orders = order
    if len(orders) == 1:
        return 1
    
    time = 0
    queue = deque()
    queue.append((menu[orders[0]]))# 첫 번째 주문 소요시간
    orders = orders[1:]
    
    for order in orders:
        time += k
        answer = max(answer, len(queue))
        if len(queue) >= 1:
            left_time = queue.popleft()
            left_time -= k
            if left_time > 0: # 제작이 완료되지 않았으면
                queue.appendleft(left_time)
            
            elif left_time < 0:
                while True:
                    if len(queue) >= 1:
                        tmp = queue.popleft()
                        tmp += left_time
                        if tmp > 0: # 제작이 완료되지 않았으면
                            queue.appendleft(tmp)
                            break
                        elif tmp == 0:
                            break
                        else:
                            left_time = tmp
                                
        queue.append(menu[order]) 
        answer = max(answer, len(queue))

    return answer

아이디어

일단 데크 자료형을 사용하였다. 양쪽에서 데이터를 빼고 넣을 수 있기 때문에.

그럼 크게는 세 가지 케이스가 생긴다.

1. 다음 k초 뒤에 작업이 끝나지 않은 경우

2. 다음 k초 뒤에 작업이 딱 맞춰 끝난 경우

3. 다음 k초 뒤에 작업이 이미 끝나있는 경우

 

1번은 다음 큐에서 꺼낸 주문 처리중의 잔여시간을 다시 큐에 넣어주면 된다. (k를 뺀 수 다시 넣기)

2번은 큐에서 다시 넣지 않고 그냥 다음 주문을 큐에 넣는다

3번은 만약 큐에 대기중인 주문이 있다면 k-(이전 음료 처리 시간) 만큼 작업을 수행해주면 된다.

 

코드는 위 로직대로 짠 것 같은데, 시간초과가 난다. 아직 효율성 부분이 너무너무 약하다

 

그럼 정답을 찾아보자 !

def solution(menu, order, k):
    answer = []
    queue = []
    orders = order
    
    for order in orders:
        queue.append(menu[order])
        answer.append(len(queue))
        
        queue[0] = queue[0]-k # 주문 시간 차감
        
        # 차감 결과가 음수라면 바로 다음 주문의 제조 시간 차감
        # 음수가 된 주문 리스트에서 제거하여 다음 손님이 제일 앞 손님이 됨
        while queue and queue[0] <= 0:
            if queue[0] <= 0:
                if len(queue) >= 2:
                    queue[1] = queue[0]+queue[1]
                queue.pop(0)
    
    return max(answer)

일단 deque를 안쓰고 그냥 queue를 써주면 됐었다.

그리고 복잡하게 할 필요 없이 그냥 아직 안 끝난 경우는 값만 업데이트 해주면 되고, 이미 끝난 경우는 저렇게 처리해주면 된다 .. 

 

배운점

max()를 반복문 안에 써주기보단 리스트에 추가하고 마지막에 한 번 max() 함수를 써주는게 효율성 측면에선 더 좋다.

무작정 코드 짜지 말고 더 간단하고 효율적인 방법을 먼저 생각하자. (문제 단순화)

while queue and queue[0] <= 0: 이런식으로 코드를 짧게 쓰는 연습을 하자.

 

궁금한점

queue와 deque의 정확한 차이가 뭘까 ?? 

큐 : "선입선출 구조"

덱 : 앞뒤에서 입력과 출력이 모두 가능한 형태

 

 이 문제에선, 앞에선 빼기만 하고 뒤에 넣기만 하니 굳이 덱을 사용할 필요가 없다. 

 

참고

https://velog.io/@sonada903/PCCP-%EB%AA%A8%EC%9D%98%EA%B3%A0%EC%82%AC2-3%EB%B2%88-%EC%B9%B4%ED%8E%98%ED%99%95%EC%9E%A5