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

문제

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

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

설명

처음엔 이걸 어떻게 풀어야 하지? 다리만큼 배열을 써서 트럭이 지나가는 것처럼 해야 하나...?

별별 생각이 다 들었다.

하지만 이 문제가 스택 / 큐 문제로 분류된 만큼 생각을 해보니 큐로 간단히 풀 수 있다!

큐를 다리라고 생각하고, 조건에 맞게 트럭을 큐에 넣고 빼면서 다리에 오르고 건너는 것을 구현하면 된다.

 

고려해야 할 조건

• 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있다.
• 트럭이 다리에 올라가면 1초가 시작되는 것.
• 그 후 다리 위에서 1칸씩 움직일 때마다 역시 1초가 흘러감.

 

Queue를 다리라고 생각했을 때 어떤 식으로 큐에 트럭을 넣고 빼야 할까

 

 

 

예제 1을 그림으로 나타내면 위와 같다.

다리를 나타내는 큐가 있고, 7, 4, 5, 6kg의 트럭이 순차적으로 다리를 지나갈 것이다.

다리에 트럭을 넣는 조건은 총 3가지가 있다.

 

1. 큐가 비어있는 경우
2. 큐가 (다리 길이만큼) 가득 차지 않은 경우
3. 큐가 가득 찬 경우

 

 

 

 

큐가 비어있는 경우는 다리에 어떠한 트럭도 올라가지 않은 경우와 같다.

이럴 땐 그냥 트럭을 다리에 올려주면 된다 => 큐에 넣어주면 됨

그리고 현재 다리에 있는 트럭의 무게를 저장할 sum값에 올라간 트럭의 무게를 더해준다.

그리고 트럭이 다리 위에 올라갔으니 시간은 + 1

 

 

 

 

 

 

두 번째로 큐가 가득 차지 않은 경우이다.

이 때는 이미 다리에 있는 트럭의 무게와 다리에 올릴 다음 트럭의 무게를 비교해 다리에 올릴지 말지를 결정해야 한다.

최대 무게가 10이고 현대 다리에 있는 트럭의 무게는 7이다.

만약 다음 트럭이 4kg라면 전체 무게가 11이 돼서 다리에 올릴 수 없다.

따라서 큐에 이미 있는 트럭이 다리를 지나갈 수 있도록 0 값을 넣어준다.

 

하지만 만약 다음 트럭이 3kg라면 전체 무게가 10이기 때문에 다음 트럭을 올리고 현재 무게에 다음 트럭의 무게를 더해준다.

이 두 과정 모두 트럭을 0이든 n kg이든 올리기 때문에 시간은 + 1

 

 

 

 

 

 

마지막으로 큐가 가득 찬 경우이다.

이때는 가장 앞에 넣은 트럭이 다리의 끝에 도달했다는 것이다

poll() 메서드를 이용해 트럭을 꺼내 줌으로써 다리를 건너도록 해준다.

다리에서 내릴 때는 시간이 들지 않는다.

 

이 과정을 전체 트럭의 개수만큼 반복하면 된다!

그리고 아래 코드의 반복문의 특성상 마지막 트럭의 경우 다리에는 올랐지만 다 건너지 못한다.

그래서 정답을 출력할 때는 지금까지 걸린 time에 마지막 트럭이 건너는데 걸리는 시간인 다리의 길이를 +해서 출력하면 된다.

전체 코드

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 i = 0; i < truck_weights.length; i++) { // 향상된 for문을 쓰는게 좋을 것 
			int truck = truck_weights[i];

			while(true) {
				// 큐에 아무것도 없는 경우 = 어떠한 트럭도 다리위에 없음 
				if(queue.isEmpty()) { 
					queue.add(truck);
					sum += truck;
					time++; // 다리에 오를 때만 시간 추가 
					break;
				} else if(queue.size() == bridge_length) { // 큐에 다리 길이만큼 트럭이 다 찬 경우 
					sum -= queue.poll();
				} else  { // 다리 길이만큼 큐가 차지않았음
					// weight 값을 넘지 않는 선에서 새로운 트럭을 다리에 올려줌 
					if(sum + truck <= weight) {
						queue.add(truck);
						sum += truck;
						time++;
						break;
					} else { 
						// 넘는다면 0을 넣어 이미 큐에 있는 트럭이 다리를 건너게 만듬 
						queue.add(0);
						time++;
					}
				}
			}
		}

        // 마지막 트럭에서 반복문이 끝나는데, 마지막 역시 다리 길이만큼 지나가야하기에 + 다리 길이 
		return time + bridge_length; 
    }
}

GITHUB

https://github.com/KwonMinha/Programmers/blob/master/Level2/src/Truck.java

KwonMinha/Programmers