[프로그래머스 Level 2] 다리를 지나는 트럭 / (스택/큐) / 파이썬

<문제>

 

 

<풀이>

 

def solution(bridge_length, weight, truck_weights):
    time = 0
    truck = truck_weights[::-1]			# (1)
    bridge = []
    input = []
    while not (len(bridge) == 0 and len(truck) == 0):		# (2)
        time += 1
        # print(time, 'AM: ', bridge, input)
        if len(input) > 0:
            if time - input[0] == bridge_length:
                bridge.pop(0)
                input.pop(0)
        if len(truck) != 0:
            go = truck.pop()
            if (len(bridge) + 1 <= bridge_length) and (sum(bridge) + go <= weight):
                bridge.append(go)
                input.append(time)
            else:
                truck.append(go)
        # print(time, 'PM: ', bridge, input)
    return time

 

 

코드 설명:

 

스택.큐 구조로 푼다는 것은 주어진 리스트의 길이를 N이라 할 때 알고리즘이 O(N)이어야 한다. 다만 이 문제는 다리의 길이와 버틸 수 있는 무게라는 조건이 있기 때문에 조금 달라진다. 그러나 주어진 리스트를 다룰 때 O(N)에 해당하는 연산을 쓰게 되면 시간이 늘어나므로 이 부분에서 주의해야 한다.

 

(1)

이전에 작성한 스택에 관한 글에서 stack은 pop()과 append()로 구현한다고 했다. LIFO구조이기 때문이다. 문제 예시를 보면 알 수 있듯이 truck_weight의 0번째부터 넣는 구조라서 pop(0)을 쓰게 되면 O(N)이 돼서 효율성이 나빠진다. 그래서 pop()을 쓸 수 있게끔 처음에 truck_weight를 뒤집었다. 

 

bridge는 다리를 건너는 중인 트럭들을 나타낼 리스트고, input은 bridge에 있는 트럭들이 들어간 시간을 담을 리스트다. 반복문은 bridge와 truck이 전부 다 빌 때까지 진행하고. 한 번 루프가 돌때마다 time을 1씩 늘린다. 최종적으로는 while문이 빠져나온 순간의 time이 return하면 된다.

 

(2)

while문 안을 살펴보자. 트럭이 다리에서 빠지는 것을 먼저 처리하고 대기하고 있는 트럭이 들어가게 했다. (이 순서는 하기에 따라 바뀌어도 상관 없을듯) 1초에 1칸씩 움직이니까 현재 시간과 들어간 시간의 차이가 다리길이만큼 같으면 다리를 건넌 것으로 보고 bridge와 input에서 각각 맨 처음 있는 값들을 지운다. 그 다음 대기하고 있는 트럭이 있을 때 길이 제한과 무게 제한 조건을 만족하는지 따져보고 넣을지 말지를 결정한다. 

 

---

+@ 

Q. pop() 대신 pop(0)을 쓰면 왜 효율성이 나빠지나??

A. 파이썬에서 pop 연산을 처리하면서 리스트에 남은 element들의 index를 건드리기 때문이다.

[1,2,3] 라는 list가 있다고 하고, 여기서 pop()을 쓰면 맨 끝의 3이 빠진다. 1과 2의 index는 빠지기 전인 0과 1 그대로 유지된다. 3 하나만 처리하면 되는 것이다. O(1)에 해당한다. 이번엔 반대로 [3,2,1] 라는 list가 있다고 하고 pop(0)을 써보자. 3이 빠지는 것은 똑같은데 1과 2의 index가 한 칸씩 땡겨진다. 빠지는 숫자 외에 남아있는 숫자들의 index도 처리해야하니 O(N)이 되어버린다. 

 

+@

Q. 다리를 건너는 과정에서 bridge와 input에서 pop(0)을 썼는데...?

A. 다리의 무게 제한과 길이 제한때문에 truck에서 pop을 하는 횟수 >> 다리 안에 있는 트럭에서 pop을 하는 횟수 라고 생각하여서 효율성에 크게 지장이 없을 것이라 생각한다.

 

---

##

1. truck이 주어진대로 빠지는 것인데 조건을 무조건 빨리 나가는 것으로 보고 정렬하고 난리도 아니었다. 헛고생... 프로그래머스 문제는 조건을 꼼꼼히 읽어야 한다.

 

2. 처음에 뒤집지 않고 pop(0)을 써서 해결하는 경우도 통과하긴 한다. 다음은 코드와 시간을 비교해본 것이다.

 

def solution(bridge_length, weight, truck_weights):
	'''reverse (x)''' 
    time = 0
    bridge = []
    input = []
    while not (len(bridge) == 0 and len(truck_weights) == 0):
        time += 1
        print(time, 'AM: ', bridge, input)
        if len(input) > 0:
            if time - input[0] == bridge_length:
                bridge.pop(0)
                input.pop(0)
        if len(truck_weights) != 0:
            go = truck_weights.pop(0)
            if len(bridge) + 1 <= bridge_length and sum(bridge) + go <= weight:
                bridge.append(go)
                input.append(time)
            else:
                truck_weights.insert(0, go)
        print(time, 'PM: ', bridge, input)
    return time

 

뒤집고 나서 pop()을 썼을 때 시간.

 

안 뒤집고 pop(0)을 쓸 경우

전자의 경우가 전체적으로 빠르고, 테스트 2 4 5 6에서 확연한 차이가 남을 알 수 있다.