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

💡 문제 다리를 지나는 트럭 (https://school.programmers.co.kr/learn/courses/30/lessons/42583)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

큐(Queue)는 컴퓨터 과학에서 사용하는 자료 구조 중 하나로, 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 원칙을 따릅니다. 큐는 일상생활에서 줄을 서서 차례를 기다리는 상황을 생각하면 이해하기 쉽습니다. 예를 들어, 사람들은 줄의 맨 앞에서 차례를 기다리며, 새로 온 사람들은 줄의 맨 뒤에 서게 됩니다.

---

큐의 기본 동작

1. 삽입(Enqueue): 요소를 큐의 뒤쪽에 추가합니다.
2. 삭제(Dequeue): 요소를 큐의 앞쪽에서 제거합니다.
3. 확인(Peek or Front): 큐의 앞쪽에 있는 요소를 반환하지만 제거하지 않습니다.
4. 비어있는지 확인(Empty): 큐가 비어 있는지 확인합니다.

큐의 특성

• FIFO(First In First Out): 큐에 먼저 들어온 요소가 먼저 나갑니다.
• 양쪽이 열려 있는 구조: 한쪽 끝에서는 요소를 추가하고, 다른 쪽 끝에서는 요소를 제거합니다.

큐의 구현

큐는 배열이나 연결 리스트를 이용해 구현할 수 있습니다. Java에서는 큐를 구현하기 위해 **LinkedList**나 ArrayDeque 클래스를 사용할 수 있습니다.

큐의 사용 예시

• 프린터 작업 대기열: 프린터는 먼저 요청된 작업을 먼저 처리합니다.
• 프로세스 관리: 운영체제에서 여러 프로세스가 CPU를 사용할 때 큐를 사용해 공정하게 처리합니다.
• 데이터 스트리밍: 네트워크 패킷을 순서대로 처리하기 위해 큐를 사용합니다.

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

public class QueueExample {
    public static void main(String[] args) {
        // 큐 생성
        Queue<Integer> queue = new LinkedList<>();
        
        // 큐에 요소 삽입
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        // 큐의 앞쪽 요소 확인
        System.out.println("Front element: " + queue.peek());

        // 큐에서 요소 제거
        System.out.println("Removed element: " + queue.poll());

        // 큐의 상태 확인
        System.out.println("Queue contents: " + queue);

        // 큐가 비어있는지 확인
        System.out.println("Is queue empty? " + queue.isEmpty());
    }
}

---

🤓 문제 풀이

이 문제는 트럭들이 다리를 건너는 특정 조건을 만족하면서 최소 시간을 계산해야 합니다. 

1. 큐 사용: 다리를 건너고 있는 트럭을 큐로 관리합니다.
2. 시간 관리: 다리를 건너는 시간과 트럭의 이동을 시뮬레이션합니다.
3. 트럭 무게 관리: 현재 다리에 있는 트럭의 무게를 추적하여 새로운 트럭이 다리에 올라갈 수 있는지 확인합니다.

주요 과정

• 큐에 트럭을 추가할 때 현재 다리의 무게와 길이를 확인합니다.
• 큐에서 트럭을 제거할 때 시간을 증가시키고 현재 무게를 갱신합니다.
• 트럭이 다리를 모두 건널 때까지 이 과정을 반복합니다.

주요 키워드

1. 큐(Queue): FIFO(First In First Out) 방식의 자료 구조로, 트럭들이 다리를 건너는 순서를 관리하는 데 유용합니다.
2. 무게 제한(Weight Limit): 다리가 견딜 수 있는 최대 무게를 초과하지 않도록 관리해야 합니다.
3. 다리 길이(Bridge Length): 다리 위에 동시에 올라갈 수 있는 트럭의 최대 수를 제한합니다. 

---

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

public class Main {
    /**
     * @param bridge_length 다리의 길이 (한 번에 다리 위에 있을 수 있는 최대 트럭 수)
     * @param weight        다리가 견딜 수 있는 최대 무게
     * @param truck_weights 트럭들의 무게 배열
     * @return 모든 트럭이 다리를 건너는데 걸리는 최소 시간
     */
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0; // 경과 시간
        int currentWeight = 0; // 현재 다리에 있는 트럭들의 총 무게

        Queue<Integer> bridge = new LinkedList<>(); // 다리를 건너는 트럭들을 관리할 큐

        // 초기 상태 : 다리가 올라가 있는 트럭이 없으므로 bridge_length 크기만큼 0을 채워넣음
        for (int i = 0; i < bridge_length; i++){
            bridge.add(0);
        }

        int index = 0; // 대기 트럭 배열의 인덱스

        // 모든 트럭이 다리를 건널 때까지 반복
        while (!bridge.isEmpty()){
            // 1초가 지남을 표현
            answer++;
            // 다리가 건넌 트럭을 큐에서 제거하고, 현재 다리의 총 무게에서 제외
            currentWeight -= bridge.poll();

            // 대기 트럭이 남아 있고, 현재 다리의 무게 제한을 넘지 않으면 트럭을 다리에 올림
            if (index < truck_weights.length){
                if (currentWeight + truck_weights[index] <= weight){
                    // 새로운 트럭을 다리에 올림
                    bridge.add(truck_weights[index]);
                    currentWeight += truck_weights[index];
                    index++;
                } else {
                    // 무게 제한을 넘으면 빈 자리를 유지 (0을 추가한다.)
                    bridge.add(0);
                }
            }
        }

        return answer; // 모든 트럭이 다리를 건너는데 걸리는 최소 시간 반환
    }

}

---

📚 풀이 보완

코드 설명

1. 초기 상태 설정:
   • currentWeight는 현재 다리 위의 트럭들의 총 무게를 추적합니다.
   • bridge는 다리 위의 트럭을 나타내는 큐로, 초기에는 bridge_length만큼 0을 채워 넣습니다.
2. 시간 경과 관리
   • 매 초마다 시간 answer를 증가시키고, 큐의 맨 앞(다리를 건넌 트럭)을 제거하여 currentWeight에서 해당 무게를 뺍니다.
   • 새로운 트럭을 다리에 올릴 수 있는지 확인합니다. 가능하면 큐에 추가하고 currentWeight를 갱신합니다.
   • 무게 제한을 넘는다면 빈 자리를 유지하기 위해 0을 추가합니다.
3. 결과 반환:
   • 모든 트럭이 다리를 건넌 후, answer를 반환합니다.

---

1. 큐 초기화:
   • Queue<Integer> bridge = new LinkedList<>();: 트럭들이 다리를 건너는 순서를 관리할 큐를 초기화합니다.
   • for (int i = 0; i < bridge_length; i++) { bridge.add(0); }: 초기 상태로 다리에 트럭이 없으므로 **bridge_length**만큼 0을 채워넣습니다.

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

2. 트럭이 다리를 건너는 과정:
   • while (!bridge.isEmpty()): 모든 트럭이 다리를 건널 때까지 반복합니다.
   • answer++: 1초가 지났음을 표현합니다.
   • currentWeight -= bridge.poll();: 다리를 건넌 트럭을 큐에서 제거하고, 현재 다리의 총 무게에서 제외합니다.
   • 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); }: 무게 제한을 넘으면 빈 자리를 유지합니다.

   while (!bridge.isEmpty()){
       // 1초가 지남을 표현
       answer++;
       // 다리가 건넌 트럭을 큐에서 제거하고, 현재 다리의 총 무게에서 제외
       currentWeight -= bridge.poll();
   
       // 대기 트럭이 남아 있고, 현재 다리의 무게 제한을 넘지 않으면 트럭을 다리에 올림
       if (index < truck_weights.length){
           if (currentWeight + truck_weights[index] <= weight){
               // 새로운 트럭을 다리에 올림
               bridge.add(truck_weights[index]);
               currentWeight += truck_weights[index];
               index++;
           } else {
               // 무게 제한을 넘으면 빈 자리를 유지 (0을 추가한다.)
               bridge.add(0);
           }
       }
   }
   

📍 Plus+