[백준/JAVA] 13335번: 트럭

📖 문제

13335번: 트럭

 

 

💡  풀이 방식

• 큐

필요 자료구조
- 오른쪽에 위치한 트럭들 저장용 큐 trucks
- 크기가 w인 다리 위의 트럭들 저장용 큐 bridge
- 다리 위의 트럭들의 무게 합 나타낼 int형 변수 sum

 

1. 두 큐에 초기값들을 넣는다.

  - trucks 큐에는 입력받은 트럭들을 추가한다.

  - bridge 큐에는 w 길이만큼 0을 추가한다.

 

2. 다리 위가 빌 때까지 아래 과정을 반복한다.

  2-1) 시간 +1초 소요

  2-2) 다리의 맨 왼쪽에 있는 트럭이 내려간다.

  2-3) 트럭 저장 큐가 비어있지 않고, 맨 앞에 있는 트럭과 현재 다리 위의 트럭들의 무게의 합을 더한 값이 최대 하중보다 작거나 같다면, 맨 앞의 트럭을 다리 위로 올린다. 그게 아니라면, 다리에 0을 추가한다.

 

과정샷

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int n,w,L;
    static Queue<Integer> trucks = new LinkedList<>();  // 트럭 무게 저장용 큐
    static Queue<Integer> bridge = new LinkedList<>();  // 다리 위에 있는 트럭 저장용 큐
    static int time = 0;
    static int sum = 0;    // 다리 위 트럭들의 무게의 합
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        n = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < n ; i++) {
            trucks.add(Integer.parseInt(st.nextToken()));
        }
        
        // 💥 다리 길이만큼 0 저장해두기
        for(int i = 0 ; i < w;  i++) bridge.add(0);
        
        while(!bridge.isEmpty()) {  // 다리 위가 빌 때까지 반복문 수행
            time++;
            sum -= bridge.poll();
            
            if(!trucks.isEmpty()) {
                if(trucks.peek() + sum <= L) {  // 다리 위에 트럭 올리기
                    sum += trucks.peek();
                    bridge.add(trucks.poll());
                }
                else {  // 💥 최대 하중 초과 시, 다리 위에 아무것도 안 올림 (0은 큐 자리차지용)
                    bridge.add(0);
                }
            }
        }
        
        System.out.println(time);
    }
}
 

 

 

---

💦 어려웠던 점

- 큐 2개 사용할 아이디어까진 생각했는데, 큐 중 하나를 0부터 다리 위까지라고 생각했었다... ⇒ 그게 아니고 다리 길이 w만큼의 크기를 가진 큐를 활용하는 것이었다.

- 그냥 오른쪽에서 왼쪽으로 나간다는 거 자체가 그냥 큐 FIFO 그 자체인데 왜 큐라는 걸 빠르게 눈치채지 못 하였나,,,,

- 트럭이 빌 때까지 하면 되겠지~하고 while문 돌렸었다ㅎㅎ ⇒ 다리 위가 빌 때까지 하는 것이 기준!!

 

🧐 새로 알게 된 내용

- 다리 위의 트럭들 저장용 큐를 만들 아이디어

- 그리고 이 큐에 트럭을 올릴 수 없을 때는 비게 두지 말고 0을 넣어 무게에 변동은 없되 자리 차지만 하게 하자..!!!!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준 / 13335 ] 트럭 - java : Queue