[프로그래머스] (Java) 다리를 지나는 트럭 (스택/큐)

📑 1. 문제설명

---

💡 2. 접근방식

 

Queue

트럭 진입 로직: 다리의 맨 앞 트럭이 나가고 새로운 트럭이 다리에 올라갈 수 있는지 확인한 후 다리에 추가

이동시간: 트럭이 다리 위에 오르면 매 1초마다 한 칸씩 앞으로 이동함.

조건 검사: 다리가 견딜 수 있는 무게를 초과하지 않는 경우에만 트럭을 추가하며, 그렇지 않으면 0을 추가해서 빈 공간 만들기

 

• bridge_length 사이즈의 Queue 만들고 0값으로 초기화(다리에 트럭 하나도 없는 상태)
• 변수 currentWeight 현재 다리 위의 총 무게 
• 변수 time 경과시간(문제에서 return할 값)
• 다리의 길이가 1이거나 트럭의 개수가 1 일때는 해당 time 먼저 return
• 트럭의 갯수만큼 아래의 과정을 반복

1. 다리의 앞부분 트럭은 큐에서 제거

2. 다음 트럭이 다리에 진입할 수 있는지 확인

 -  현재 다리 위에 있는 트럭 무게 vs 다리로 들어올 트럭 무게 비교

3. 무게 조건에 맞는가?

 - (Yes) 새로운 트럭이 다리로 올라 감

 - (No) 견딜 수 있는 무게보다 크면 큐에 0 추가

2. 매 반복마다 time++

5. 모든 트럭이 다리를 건너면 종료

 

다리에서 트럭이 나가면 currentWeight에서 맨 앞 트럭의 무게를 빼줌

다리에 트럭이 올라가면 currentWiehgt에 새로운 트럭의 무게를 더해줌 

 

---

⭐ 3. 코드

첫번째 시도 틀림

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        // 다리 길이만큼 큐 선언
        Queue<Integer> bridge = new LinkedList<>();
        // 걸리는 총 시간
        int time = 0;
        // 현재 다리 위의 무게
        int currentWeight = 0;
        
        for(int i = 0; i < bridge_length; i++) {
            bridge.add(0);
        }
        // 현재 다리에 오를 트럭의 인덱스
        int index = 0;
        
        // 아직 다리에 올라가지 않은 트럭이 남아있는지
        // 현재 다리 위에 트럭이 남아있는지
        while(index < truck_weights.length || currentWeight > 0) {
            time++;
            
            // 다리의 맨 앞 트럭이 나감
            int leftTruck = bridge.poll();
            currentWeight -= leftTruck;
            
            // 다음 트럭이 다리에 진입할 수 있는지 조건 확인
            if(index < truck_weights.length) {
                if(currentWeight + truck_weights[index] <= weight){
                    // 트럭이 다리에 진입
                    bridge.add(truck_weights[index]);
                    currentWeight += truck_weights[index];
                    index++; 
                }
            } else {
                // 트럭이 다리에 진입할 수 없으면 빈 공간 추가
                bridge.add(0);
            }
        }
        return time;
    }
}

 

 

트럭이 다리 위로 진입하는 조건에 오류가 있었다. index < truck_weights.length만 체크하고 있으나, 다리 위에 여유 공간이 있는지는 확인하는 코드가 빠져 있는 것이다. 즉, 트럭이 다리에 진입하는 조건을 제대로 검토하지 않았기 때문에 테스트 케이스 2개만 통과되고 하나는 통과되지 못했다. 

 

트럭이 진입할 수 없을 때 빈 공간을 추가해 주어야 하는데, index가 다리 길이를 넘어갈 때만 공간을 추가하도록 코드를 잘못 짰다. 다리의 빈 공간을 추가하는 부분은 트럭이 다리에 진입할 수 없는 경우에만 발생해야 하므로 else문을 if (index < truck_weights.length) 안에 넣어야 한다. 

 

정답코드

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        // 다리 길이만큼 큐 선언
        Queue<Integer> bridge = new LinkedList<>();
        // 걸리는 총 시간
        int time = 0;
        // 현재 다리 위의 무게
        int currentWeight = 0;
        
        for(int i = 0; i < bridge_length; i++) {
            bridge.add(0);
        }
        // 현재 다리에 오를 트럭의 인덱스
        int index = 0;
        
        // 아직 다리에 올라가지 않은 트럭이 남아있는지
        // 현재 다리 위에 트럭이 남아있는지
        while(index < truck_weights.length || currentWeight > 0) {
            time++;
            
            // 다리의 맨 앞 트럭이 나감
            int leftTruck = bridge.poll();
            currentWeight -= leftTruck;
            
            // 다음 트럭이 다리에 진입할 수 있는지 조건 확인
            if(index < truck_weights.length) {
                if(currentWeight + truck_weights[index] <= weight){
                    // 트럭이 다리에 진입
                    bridge.add(truck_weights[index]);
                    currentWeight += truck_weights[index];
                    index++; 
                } else {
                    // 트럭이 다리에 진입 할 수 없으면 빈 공간 추가
                    bridge.add(0);
                }
            } else {
                // 트럭이 다리에 진입할 수 없으면 빈 공간 추가
                bridge.add(0);
            }
        }
        return time;
    }
}

 

근데 왜 index > truck_weight[index] 일 때는 bridge.add(0)로 빈 공간을 추가 해 줘야 하는거지?

 

index > truck_weight[index] 상태

index가 truck_weights.length보다 커지는 경우는 모든 트럭이 다리 위로 올라갔을 때를 의미한다. 즉, 더 이상 진입할 트럭이 없다는 뜻이다.

 

왜 bridge.add(0)을 추가하는가?

트럭이 다리 위에 올라가면, 다리 위에서 트럭들이 이동하면서 매초마다 한 칸씩 앞으로 나아간다. bridge.add(0)을 추가하는 이유는 다리 길이가 고정되어 있기 때문이다. 트럭이 다리 위로 올라가고, 매초마다 하나씩 전진하면서 빈 공간을 채워야 트럭들이 정상적으로 이동하기 때문이다. 

 

---

 

👉🏻 4. 같은 유형 문제

[프로그래머스] (Java) 주식가격 (스택/큐)

 

[프로그래머스] (Java) 프로세스 문제풀이 (스택/큐)

 

[프로그래머스] (Java) 올바른 괄호 문제풀이 (스택/큐)

 

[프로그래머스] (Java) 기능개발 (스택/큐)

 

[프로그래머스] (Java) 같은 숫자는 싫어 문제 풀이 (스택/큐)