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

💡문제 분석 요약

트럭들이 다리를 순서대로 건너는 상황이다. 다리에는 동시에 최대 bridge_length 대의 트럭이 올라갈 수 있고, 다리가 견딜 수 있는 최대 무게는 weight 이다. 모든 트럭이 다리를 건너는데 걸리는 최소 시간을 구하는 문제이다.

 

💡알고리즘 설계

• 하나의 큐를 사용한다.
  • pass_q: 다리 위에 있는 트럭들의 무게 저장
• 시간(answer)를 1초씩 증가시키며, 매초마다 작업을 수행한다.
  1. 다리를 완전히 건넌 트럭 처리
     • pass_q의 크기가 bridge_length 이상이면, 가장 앞의 트럭을 제거하고 총 무게에서 뺀다.
  2. 트럭이 다리에 올라올 수 있는지 확인
     • 대기 중인 트럭이 있고, (현재 다리 위 무게 + 대기 중인 첫 번째 트럭의 무게)가 weight 이하일 경우
     • 새 트럭을 pass_q에 추가하고, 총 무게에 더함.
     • 조건에 만족하지 못하면, 0을 pass_q에 추가한다. (트럭의 이동 시간을 위해)
  3. 다리 위 총 무게가 0이 되면 작업을 종료한다. (모든 트럭이 다리를 통과한 경우)

 

💡코드

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

class Solution {
    public static int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 1;
        int index = 0;
        Queue<Integer> pass_q = new LinkedList<>();

        int weight_sum = 0;
        while (true) {
            // 다리를 완전히 건넌 조건
            if(pass_q.size() >= bridge_length) {
                int weight_minus = pass_q.poll();
                weight_sum -= weight_minus;
            }

            // 다리에 올라가는 조건
            if(index < truck_weights.length && (weight_sum + truck_weights[index]) <= weight) {
                weight_sum += truck_weights[index];
                pass_q.offer(truck_weights[index]);
                index++;
            }
            else pass_q.offer(0);

            // 모든 트럭이 다리를 건너면 종료
            if(weight_sum == 0) break;

            answer++;
        }

        return answer;
    }
}

 

💡시간복잡도

트럭의 수를 N이라고 할 때, O(N * bridge_length) 이다.

 

💡다른 풀이

좀 더 효율적인 코드를 찾아봤다.

• 다리를 처음부터 0으로 채워 초기화한다.
  • 매 반복마다 다리 길이를 체크할 필요 없어짐.
• 매 반복마다 weight_sum이 0인지 확인하는 조건을 제거한다.
• 모든 트럭이 다리에 진입했을 때 루프를 종료한다.
• 루프 내에서 매번 시간을 증가시키고, 마지막에 시간과 다리 길이를 한 번에 더한다. (answer)

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

class Solution {
    public static int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> bridge = new LinkedList<>();
        int answer = 0;
        int currentWeight = 0;
        int truckIndex = 0;

        for (int i = 0; i < bridge_length; i++) {
            bridge.offer(0);
        }

		// 모든 트럭이 다리에 진입할 때까지 반복
        while (truckIndex < truck_weights.length) {
            answer ++;
            
            // 다리를 완전히 건넌 트럭 제거 & 무게 계산
            currentWeight -= bridge.poll(); 

			// 다리에 올라가는 조건
            if (currentWeight + truck_weights[truckIndex] <= weight) {
                bridge.offer(truck_weights[truckIndex]);
                currentWeight += truck_weights[truckIndex];
                truckIndex++;
            } else {
                bridge.offer(0);
            }
        }

        return answer + bridge_length;
    }
}

이 코드의 시간복잡도는 O(n) 이다. (n은 truck_weights 배열의 길이)

 

💡 느낀점 or 기억할정보

효율적인 방법을 한 번에 생각해내는 것이 어렵게 느껴졌다. 문제를 해결하더라도 다른 풀이를 더 찾아보고 코드를 개선하는 과정이 필요할 것 같다.