[알고리즘 / 프로그래머스] 다리를 지나는 트럭

programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭

문제는 위와 같으며 큐를 사용하여 문제를 풀 수 있습니다.

다리를 하나의 큐라고 생각하고 각 경우를 확인하며 트럭이 다리를 건널 수 있도록 하였습니다.

 

먼저 다리로 사용할 큐를 생성한 뒤, 트럭의 수만큼 반복을 진행합니다. 이는 모든 트럭이 다리 위로 올라갈 때까지 반복하는 것입니다.

 

이후 각 트럭에 대해서 아래와 같은 조건을 확인합니다.

 

CASE 1. 다리가 비어 있는 경우

이 경우는 현재 대기중인 트럭을 다리 위로 올리면 됩니다. 다리 큐에 트럭을 추가하고 시간을 + 1 하고 다리 위 트럭의 무게를 방금 추가한 트럭의 무게만큼 증가시킨 뒤, 이 트럭에 대한 확인을 종료합니다. (다리에 트럭이 올라갔으므로 종료)

 

CASE 2. 현재 다리 위에 트럭이 모두 찬 경우

이 경우는 다리 위에 있는 첫번째 트럭을 뽑아내고 다리 위의 트럭의 무게에서 빼낸 트럭의 무게를 뺍니다. 아직 다음 트럭을 추가하지 않았기 때문에 남은 조건을 계속 확인하도록 합니다.

 

CASE 3-1. 다음 트럭의 무게와 현재 다리 위 트럭의 무게를 더해서 다리가 허용하는 무게보다 큰 경우

이 경우는 다리 위로 다음 트럭을 올릴 수 없기 때문에 임시 데이터인 0을 추가하고 시간을  + 1 합니다. 다음 트럭이 다리 위로 올라간 것이 아니기 때문에 계속 반복하며 다른 조건들을 확인합니다.

 

CASE 3-2. 다음 트럭의 무게와 현재 다리 위 트럭의 무게를 더해서 다리가 허용하는 무게보다 작거나 같은 경우

이 경우는 다음 트럭이 다리 위로 올라갈 수 있기 때문에 다리 큐에 트럭을 추가하고 시간을 + 1 하고 다리 위 트럭의 무게를 방금 추가한 트럭의 무게만큼 증가시킨 뒤, 이 트럭에 대한 확인을 종료합니다.

 

이렇게 마지막 트럭까지 다리 위로 올라가고 나면 마지막 트럭이 다리를 모두 지날 때까지만 시간을 추가하면 되므로, 지금까지 구한 시간에 다리의 길이를 더해서 반환합니다.

 

파이썬 코드는 다음가 같습니다.

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge_weight = 0

    bridge = []

    for now in truck_weights:
        while True:
            if len(bridge) == 0:  # CASE 1
                bridge.append(now)
                answer += 1
                bridge_weight += now
                break
            elif len(bridge) == bridge_length:  # CASE 2
                bridge_weight -= bridge.pop(0)
            else:
                if bridge_weight + now > weight:  # CASE 3-1
                    bridge.append(0)
                    answer += 1
                else:  # CASE 3-2
                    bridge.append(now)
                    answer += 1
                    bridge_weight += now
                    break

    return answer + bridge_length

 

자바 코드는 다음과 같습니다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;  // 걸리는 시간
        int bridge_weight = 0;  // 현재 다리 위에 올라온 트럭의 무게

        Queue<Integer> bridge = new LinkedList<>();  // 다리

        // 주어진 트럭이 모두 다리 위로 올라갈 때까지 수행
        for (int i = 0; i < truck_weights.length; i++) {
            int now = truck_weights[i];
            while (true) {
                if (bridge.isEmpty()) {  // CASE 1. 다리가 비어 있는 경우
                    bridge.add(now);  // 현재 트럭 다리 위로 올리기
                    answer += 1;  // 시간 추가
                    bridge_weight += now;  // 다리 위로 올라온 트럭 무게 증가
                    break;
                } else if (bridge.size() == bridge_length) {  // CASE 2. 다리에 올라온 트럭의 수가 다리 길이와 같은 경우
                    bridge_weight -= bridge.poll();  // 맨 처음 들어온 트럭 빼기
                } else {  // CASE 3. 위 두가지 경우가 아닌 경우 새로운 트럭을 추가하는데
                    if (now + bridge_weight > weight) {  // 다음 무게의 합이 다리 무게보다 큰 경우 (다음 트럭 추가 불가)
                        bridge.add(0);  // 임시로 0 추가
                        answer += 1;  // 시간 추가
                    } else {
                        bridge.add(now);  // 현재 트럭 다리 위로 올리기
                        answer += 1;  // 시간 추가
                        bridge_weight += now;  // 다리 위로 올라온 트럭 무게 증가
                        break;
                    }
                }
            }
        }
        return answer + bridge_length;
    }
}