Python 알고리즘 끄적끄적

시간초과 발생 요인

반복적인 SUM

• 문제 참고 : 스택/큐 - 다리를 지나는 트럭 (프로그래머스)
• sum은 시간복잡도가 O(N)인데 반복문 for이나 while을 사용하면 시간복잡도가 O(n^2)이 될 수 있음
• 아래 예시는 sum으로 인해 시간초과가 발생한 경우로 sum을 반복적으로 하는 것이 아닌 계산된 값을 이용

while len(truck_list) !=0:
    b = bridge.popleft()
    S -= b
    if S + truck_list[0] > weight: # sum 함수에서 시간 초과 발생
        time +=1
        bridge.append(0)
    else:
        t = truck_list.popleft()
        bridge.append(t)
        S += t
        time +=1
        if len(truck_list) == 0:
            time += bridge_length
            break

• 시간초과가 발생한 코드

while len(truck_list) !=0:
    bridge.popleft()
    if sum(bridge) + truck_list[0] > weight: # sum 함수에서 시간 초과 발생
        time +=1
        bridge.append(0)
    else:
        bridge.append(truck_list.popleft())
        time +=1
        if len(truck_list) == 0:
            time += bridge_length
            break
return time

 

---

STACK / QUEUE

길 건너기, 

• 문제 참고 : 스택/큐 - 다리를 지나는 트럭 (프로그래머스)
• 위치 A, 길(다리), 위치 B가 있고 위치 A에서 위치 B로 갈 때, 길(다리)를 이용하는 경우 queue를 이용하여 해결
• 길(다리)를 list가 아닌 queue로 만들어 pop, append로 대상이 지나가고 추가되는 역할을 함
  • 아래 예시는 다리를 queue로 만들어 트럭 지나가는 경우 pop, 새로운 트럭이 다리위로 올라오면 append

from collections import deque

def solution(bridge_length, weight, truck_weights):
    l = len(truck_weights)
    bridge = deque([0] * bridge_length)
    truck_list = deque(truck_weights)
    S, time = 0, 0
    
    while len(truck_list) !=0:
        b = bridge.popleft()
        S -= b
        if S + truck_list[0] > weight: # sum 함수에서 시간 초과 발생
            time +=1
            bridge.append(0)
        else:
            t = truck_list.popleft()
            bridge.append(t)
            S += t
            time +=1
            if len(truck_list) == 0:
                time += bridge_length
                break
    return time