[프로그래머스] 스택/큐 1. 다리를 지나는 트럭

문제

 

---

풀이

처음에 두 가지 방법의 풀이가 떠올랐다.

1. 다리를 지나는 트럭 큐를 만든다. 반복문을 통해 트럭을 넣고, 중량의 합이 커 다음 트럭이 지나갈 수 없을 때에는 0을 채워넣으며 time을 +1씩 증가시킨다. 모든 트럭이 통과했을 때의 time을 반환한다.

2. 위와 같은 방식이지만, 트럭이 지나갈 수 없을 때 0을 채워넣으며 반복시키는 대신, 트럭이 들어온 시간을 저장해두었다가 가장 먼저 들어온 트럭을 내보내고 그만큼의 time을 더해준다.

이 방식은 반복문이 돌아가는 횟수를 줄여주어 값이 커지면 보다 좋은 효율을 보여줄 것이라 예상했다.

 

그래서 2번방식으로 코드를 작성하였는데 구연하다가 포기함. 복잡함,,,

from collections import deque

def solution(bridge_length, max_weight, truck_weights):
    time = 1
    bridge = deque()
    bridge.append([0, 1])
    weight = truck_weights[0]
    truck_idx = 1
    
    while True:
        print(time, bridge)
        # 종료조건
        if truck_idx >= len(truck_weights) and not bridge:
            return time
        # 다 건넌 트럭 빼기
        if bridge[0][1] + bridge_length < time:
            print("first")
            weight -= truck_weights[bridge[-1][0]]
            bridge.popleft()    
        # 다음 트럭 넣기
        if truck_idx < len(truck_weights) and weight + truck_weights[truck_idx] <= max_weight:
            bridge.append([truck_idx, time])
            weight += truck_weights[truck_idx]
            truck_idx += 1
            time += 1
        # 다음 트럭 못넣으면 시간추가하고 트럭빼기
        elif truck_idx < len(truck_weights):
            print("second")
            time = bridge[0][1] + bridge_length
            print(time)
            weight -= truck_weights[bridge[0][0]]
            bridge.popleft()
       
    return time

그래서 다시 1번 방식으로 했다. 이러니까 금방풀었다 근데 느린 것 같음

def solution(bridge_length, max_weight, truck_weights):
    time = 0
    bridge = [0] * bridge_length
    
    while True:
        if len(truck_weights) <= 0 and sum(bridge) == 0:
            return time
        bridge.pop(0)
        if truck_weights and sum(bridge) + truck_weights[0] <= max_weight:
            bridge.append(truck_weights.pop(0))
        else:
            bridge.append(0)
        time += 1
    
    return time

deque는 0번째 요소를 삭제하는데 리스트보다 빠르기때문에 deque로 수정해봤다

 

from collections import deque

def solution(bridge_length, max_weight, truck_weights):
    time = 0
    truck_weight_deque = deque(i for i in truck_weights)
    bridge = deque(0 for _ in range(bridge_length))
    
    while bridge:
        bridge.popleft()
        if truck_weight_deque:
            if sum(bridge) + truck_weight_deque[0] <= max_weight:
                bridge.append(truck_weight_deque.popleft())
            else:
                bridge.append(0)
        time += 1
    
    return time

띠용? 전체적으로 빨라졌는데 5번에서 시간초과;; 왜인지는 모르겠다.

 

번외로 예전에 c++로 풀어놓은 코드가 있어 가져왔다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    vector<int> cross_bridge(truck_weights.size());
    int start = 0;
    int end = 0;
    int time = 1;
    int now_weight = truck_weights[0];
    cross_bridge[0] = 1;
    
    while(true) {
        
        if(start >= truck_weights.size()) {
            break;
        }
        
        if(cross_bridge[start] >= bridge_length) {
            now_weight -= truck_weights[start];
            start++;
        }
        
        time++;
        
        if(end < truck_weights.size() - 1) {
            if(now_weight + truck_weights[end + 1] <= weight) {
                end++;
                now_weight += truck_weights[end];
            }
        }
                
        for(int i = start; i <= end; i++) {
            cross_bridge[i]++;
        }
    }
    return time;
}

이건 더미데이터 0을 추가하는 방식이 아니고 다리를 건넌지 얼마나 되었는지 cross_bridge에 저장하고 몇 번째 트럭부터 몇 번째 트럭까지 건너고있는지 start, end에 저장하여 다리를 건너면 start, end의 위치를 조정하여 풀었다.

딱히 효율적인 방식은 아닌 것 같지만 특이한 풀이인 것 같다.

 

나중에,,, 파이썬을 잘 다루게 되면 1번 방식으로 수정해 보고 싶다.