99클럽 코테 스터디 3일차 TIL - 스택/큐

항해99 코테 스터디 3일차 문제인 프로그래머스의 '다리를 지나는 트럭'은 트럭이 순서대로 다리를 모두 지나는 최소 시간을 구하는 문제다. 난이도는 레벨2이며 Queue를 통해 해결할 수 있다.

 

오늘의 문제 - 다리를 지나는 트럭 문제 정보

문제 키워드

- 스택/큐

난이도

- Level 2

 

문제 요약

• 트럭이 순서대로 다리를 지나야 하는데, 다리에 올라가 있는 트럭 무게의 합이 최대 하중 이하여야 한다.
• 트럭이 모두 건너는 데 걸리는 최소 시간을 구하라.

 

문제 풀이 과정  

• 트럭의 순서는 정해져 있고, 매 시간마다 어떤 트럭이 올라가고 내려가는지를 확인하면 된다.
• 시간의 흐름에 따라 증가하는 변수 t를 두어 while문 내에서 로직을 처리한다.
• 매 시간마다
  • 큐의 맨앞 트럭을 확인한다. 현재 시간과 다리에 올라간 시간의 차이가 다리 길이와 같으면 큐에서 뺀다.
  • 다음으로 올라갈 트럭의 무게를 확인한다. 현재 다리에 올라간 트럭들의 무게와 다음 트럭의 무게의 합이 최대 하중보다 작거나 같으면 큐에 넣는다.
• 모든 트럭이 다리를 지나 내려오면 그때의 시간 t를 응답으로 반환한다.

코드

import java.util.*;
 
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int N = truck_weights.length;
        
        Queue<Truck> trucks = new LinkedList<>();
        int t = 0, idx = 0; // t: 현재 시간, idx: 다음으로 건널 트럭 인덱스
        int restT = N;      // 아직 건너지 않은 트럭 수
        int currentW = 0;   // 현재 다리에 올라간 트럭 무게의 합
        
        while(restT > 0) {
            // 1초 지남
            t++;
            
            // 1. 다리 위의 맨 앞 트럭이 도착한지 확인
            // 트럭이 들어간 시간과 현재 시간의 차이가 다리 길이보다 길면 pop
            if (!trucks.isEmpty()) {
                Truck first = trucks.peek();
                if (t - first.enterTime >= bridge_length) {
                    restT--;
                    currentW -= first.weight;
                    trucks.poll();
                }
            }
            
            // 2. 다리에 새 트럭을 추가할 수 있는지 확인
            // 다음 트럭이 올라가도 최대 하중을 넘지 않으면 push
            if (idx < N && currentW + truck_weights[idx] <= weight) {
                trucks.add(new Truck(truck_weights[idx], t));
                currentW += truck_weights[idx];
                idx++;
            }
        }
        
        return t;
    }
    
    class Truck {
        int weight;
        int enterTime;
        
        public Truck(int weight, int enterTime) {
            this.weight = weight;
            this.enterTime = enterTime;
        }
    }
}

• 시간복잡도: O(L*N) → 다리 길이 L, 트럭 개수 N. 모든 트럭이 한번에 하나씩만 올라갈 수 있는 경우에 걸리는 시간.
• 공간복잡도: O(N) 

 

오늘의 학습 회고

새롭게 알게된 것

• Deque는 맨앞에 추가 또는 맨뒤에서 삭제가 필요한 경우에만 사용하자. 이 문제는 그럴 필요가 없으므로 Queue로도 해결 가능하다.