[스택/큐] 다리를 지나는 트럭 - JAVA

https://programmers.co.kr/learn/courses/30/lessons/42583?language=java 

코딩테스트 연습 - 다리를 지나는 트럭

---

저번에 파이썬으로 풀 때는 이해 못했는데 이번에 이해해버림..!

설명이 너무 잘되어있는 블로그 참고하니까 쉽더라구~

 

 

자바 코드)

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> queue = new LinkedList<>();
        int sum = 0; //현재 다리 위 무게
        int time = 0; //다리를 건너는 시간
        
        for(int truck : truck_weights) {
            while(true) {
                if(queue.isEmpty()) { //큐(다리)에 아무것도 없는 경우
                    queue.add(truck); //큐(다리)에 트럭 추가
                    sum += truck; // 다리 위에 트럭 무게 추가
                    time++; //현재 트럭이 다리 위에 올라가는 시간
                    break;
                } else if(queue.size() == bridge_length) { //큐(다리)가 가득 찬 경우
                    // 다리에서 나올떄는 시간이 필요하지 않으므로 시간은 안 더해줘도 됨
                    sum -= queue.poll(); //다리의 맨 앞 트럭 빼기
                } else { //큐(다리)가 가득 차지 않은 경우
                    if(sum+truck <= weight) {
                        queue.add(truck); //큐에 트럭 추가
                        sum += truck;
                        time++;
                        break;
                    } else {
                        queue.add(0); //다음 트럭이 올라올 수 없는 경우 0을 넣어서 앞의 트럭이 건너도록 한다
                        time++;
                    }
                }
            }
        }
        return time+bridge_length;
    }
}

우선 다리를 큐로 생각하고 거기에 트럭을 하나씩 추가하고 빼는 과정을 통해 시간을 계산한다

먼저 트럭이 다리를 올라갈 때 시간이 1초 지나고 내려올 땐 시간을 고려안해도 된다

그리고 모든 트럭은 다리를 건널때 다리길이만큼의 시간이 필요하므로, 각 트럭이 다리 위에 올라가는 시간 1초와 다리 위에서 한칸씩 움직일 때마다 1초가 흐른다

 

이제 반복문을 통해 모든 트럭을 다리위에 올려준다

이 때 경우를 3가지로 나눈다

1. 큐가 비어있는 경우
2. 큐가 가득 차지 않은 경우
3. 큐가 가득 찬 경우

 

1) 우선 큐가 비어있는 경우에는 현재 반복문 상에서의 트럭을 큐에 넣어주고 시간을 1초 추가한다 -> 다리위에 올라가는 시간이 1초니까~

 

2) 큐가 가득차지 않은 경우에는 경우를 나눠서 생각해야 한다

만약 다음 트럭이 올라갈 수 있으면 큐에 트럭을 추가하고 시간을 1초 추가한다(트럭이 다리위에 올라가는 시간)

만약 다음 트럭이 못 올라가면 0을 큐에 넣어줘서 현재 다리위에 있는 트럭이 움직이도록 해준다. 그리고 시간도 1초 추가한다. 즉, 이 상황에서는 현재 다리위에 있는 트럭만 한칸씩 움직이고 시간이 1초 지난 것이다

 

3) 큐가 가득찬 경우에는 맨 앞 트럭을 다리에서 빼줘야 한다 

이 경우에는 시간은 추가되지 않는다 (다리에서 내려가는 경우에는 시간이 필요하지 않으니까)

 

 

그리고 마지막에 다리 길이를 시간에 더해주는데, 이는 코드의 반복문이 끝나면 다리위에 모든 트럭이 올라가기만 하고 끝난다

즉, 올라간 트럭들이 다리를 건너는 시간은 더해지지 않았으므로 다리 길이를 더해줘서 건너는 시간을 출력하는 것이다!

 

 

 

 

와.. 이게 이해가 되네 

아무쪼록 아래의 제가 참고한 블로그 작성자분께 감사인사를 드리며..

빠잉

 

 

 

참고) https://minhamina.tistory.com/241

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