알고리즘 문제 풀이를 블로그에 올리는 이유는 풀이, 코드를 기록하기 위함이니
앞으로 문제를 다 긁어오기보다 링크만 두고 풀이가 잘 보이도록 포스팅 할 예정입니다!

📄 문제

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

---

👩‍💻 풀이

1. 문제 이해

이 문제는 bridge_legth만큼 트럭을 다리에 올리되, 트럭 무게의 합이 weight를 넘지 않게 조절하면서
모든 트럭이 다리를 지나는데 걸리는 시간을 구하는 문제이다.

이 문제도 문제 이해가 다소 어려웠는데(또르륽💧)

• 트럭이 한 번 다리에 올라오면 다리 길이만큼은 다리 위에 머물러야하고,
• 트럭이 다리를 내려오는 것은 트럭이 다리에 올라오는 것과 동시에 가능하다.
  (= 중간 과정에서 큐가 비는 경우가 없음, 내리면서 올라옴)

입출력 예로 제시된 2, 10, [7,4,5,6]을 보자

다리의 길이는 2, 고로 다리 위의 자리는 _, _ 두 개 이다.
1초 : _,7
2초 : 7,_	=> 무게 초과로 다음 트럭이 올라오지 못함
3초 : _,4
4초 : 4,5
5초 : 5,_	=> 무게 초과로 다음 트럭이 올라오지 못함
6초 : _,6
--------------------------대기 트럭 0, 이후는 다리에서 트럭을 빼는 과정--------------------------
7초 : 6,_
8초 : _,_	=> 모든 트럭이 다리를 지남

총 8초가 걸렸기 때문에 return 값은 8이 된다.

2. 큐 활용 풀이

• 다리 역할을 할 큐 생성 (큐의 최대 사이즈 = 다리의 길이로 유지해줄 것)
• truck_weight(대기 트럭 배열)에서 truck을 하나씩 빼면서 loop
• 1) 큐가 비어있다면? (=첫번째 시도라면) → 맨 앞 트럭을 큐에 add, 초+1
• 2) 큐 사이즈 == 다리의 길이라면? → 큐의 맨 앞 값 poll
  초는 세지 않음, 이후 큐에 값을 넣을 때 함께 카운트
• 3) 그 외의 경우(큐가 비어있지도 않고, 큐가 꽉 차있지도 않은 상태)
  - 무게가 초과되지 않는다면, truck을 하나 더 add, 초+1
  - 무게가 초과된다면, 자리만 채워주기 위해 0 add, 초+1
• truck_weight(대기 트럭 배열)이 비었다면, 남은 일은 다리를 비워주는 것
  answer(초) + bridge_length(다리 길이)로 다리가 빌 때까지 시간 고려하여 return

• 주의사항)
  큐에서 poll하거나 0을 add하는 경우,
  truck 값을 넣을 때까지 더 반복해야하기 때문에 전체 구문이 while(true)문 안에 위치함
  truck 값을 넣어주고나면, 다음 truck 값으로 넘어가야하기 때문에 break하여 while문 탈출

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

public class Solution {

    // 큐 안 값의 sum을 구해주는 메소드
    static int queueSum(Queue<Integer> queue) {
        int sum = 0;
        for(int n : queue) {
            sum += n;
        }
        return sum;
    }

    public static int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> queue = new LinkedList<>();
        int size = queue.size();
        int answer = 0;

        for(int truck : truck_weights) {
        
            // truck 값 넣을 때까지 반복
            while(true) {
                if(queue.isEmpty()){
                    queue.add(truck);
                    answer++;
                    break;  // truck 값을 넣어주고 나서는 break
                } else if(queue.size() == bridge_length) {
                    queue.poll();
                } else {
                    if(queueSum(queue) + truck <= weight) {
                        queue.add(truck);
                        answer++;
                        break;  // truck 값을 넣어주고 나서는 break
                    } else {  // 무게가 초과되어 다음 truck 못 들어올 시
                        queue.add(0);
                        answer++;
                    }
                }
            }
        }
        return answer + bridge_length;  // 마지막에 들어있는 값 다 빼서 큐를 비울 때 고려 + bridge_length
    }
}