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

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

풀이과정

1. 큐에 트럭을 올리기

1-1. 올라갈 수 있으면 트럭의 무게를 offer

1-2. 올라갈 수 없으면 0을 offer (가상의 트럭)

2. 큐에서 트럭 빼주기

큐의 size가 bridge_length와 같아진다면, 제일 앞의 큐는 다리를 건너갈 수 있므로 q.pollFirst()로 큐에서 빼줘야 합니다.

3. truck_weights배열의 마지막 인덱스 트럭 고려하기

마지막 인덱스 트럭을 큐에 넣는 경우는, 이후의 트럭이 없기 때문에 q.size()==bridge_length 로직으로는 큐에서 트럭을 빼줄 수 없습니다. 아래 코드에서 if(idx==truck_weights.length) 부분 입니다.

if(q.size()+1 <= bridge_length && current_weight + w <= weight){ //다리에 트럭을 올릴 수 있으면
                q.offer(w);
                current_weight += w;
                idx += 1;
                if(idx==truck_weights.length){
                    return answer += bridge_length;
                }
            }

마지막 인덱스 트럭의 경우에는, 무게가 0인 가상의 트럭을 offer하는 경우가 없으므로 q.size는 증가하지 않습니다. 따라서 큐의 size가 bridge_length와 같아진다는 조건으로 큐에서 빼줄 수 없게 됩니다.

마지막 인덱스 트럭을 고려하기 위해서 bridge_length를 answer에 더한 뒤 return 해줘야 합니다.

처음 생각

큐에 올라간 트럭들의 현재 위치를 어떻게 구현해야 좋을지 잘 생각이 나지 않았습니다.

처음에는 Truck 클래스를 만들고, 멤버변수에 cnt 값을 주어서 매 초마다 큐의 모든 Truck 인스턴스의 cnt값을 -- 해주면 되지 않을까? 라고 생각했는데, 이 생각은 비효율 적인 알고리즘 이었습니다.

 

더 효율적인 방식이 있었습니다.

 

바로, 큐의 size 메서드를 활용하고 무게가 0인 가상의 트럭을 큐에 넣는 방식으로 구현할 수 있었습니다.

큐에 트럭이 올라갈 수 없는 경우 0 을 넣습니다.

큐 사이즈 == bridge_length 가 되면 큐 제일 앞의 값을 제거하여 트럭이 다리를 건너가는 경우를 구현할 수 있습니다.

 

알게된 점

• 가상의 트럭(무게가 0)과 큐 사이즈로 다리 건너기 로직을 구성할 수 있음을 배웠습니다.
• 이때 예외의 경우(마지막 인덱스 트럭)을 잘 고려해서 값을 갱신해줘야 함을 알게 되었습니다.

 

전체코드

import java.util.*;

class Solution {   
    
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int current_weight = 0;
        Deque<Integer> q = new ArrayDeque<>();
        int idx = 0;
        
        while(true){
            int w = truck_weights[idx];
            
            answer += 1;
            
            if(q.size()+1 <= bridge_length && current_weight + w <= weight){ //다리에 트럭을 올릴 수 있으면
                q.offer(w);
                current_weight += w;
                idx += 1;
                if(idx==truck_weights.length){
                    return answer += bridge_length;
                }
            }else{ // 트럭을 다리에 올릴 수 없으면 0 넣어주기
                q.offer(0); 
            }       
            
            if(q.size()==bridge_length){ // 큐가 가득 찬 경우 = 제일 앞에 있는 트럭이 건너가는 경우
                current_weight -= q.pollFirst();
            }
        }
            
    }
}