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

1 . 문제 설명

 

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

 

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

 

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

 

입출력 예

 

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

 

2 .  알고리즘 [풀이 방법]

 

나는 이 문제를 예시를 통해서 풀이가 어떤 경우에 따라 방식이 바뀌는지를 확인하고, 알고리즘을 세우는데 필요한 개념들을 구체화하고, 이를 코드 구현하는 방식으로 풀었다. 가장 먼저 예시를 통해서 풀이의 경우를 나누고 알고리즘을 세우는데 필요한 것들은 뽑아냈다. 

 

문제는 결국 모든 다리가 건너는 시간을 구하는것이다. 나는 예시를 통해서 총 3가지의 경우와 로 나눴다. 1. 첫번째 트럭이 처음으로 다리에 집입할 때 2. 다리에 진입할 때  3. 다리를 다 건넜을 때 이렇게다. 각각의 경우를 사진과 함께 좀 더 자세히 설명해보겠다. 

 

 

가장 먼저 첫번째 경우인 대기줄의 첫번째 트럭이 처음으로 다리에 진입할 경우다. 이 경우를 따로 뺀 이유는 예시를 통해서 반복하는 구간을 찾다가 이 처음 진입하는 구간은 어떠한 조건없이 바로 진입할 수 있으며 (애초에 다리의 수용 가능한 무게보다 큰 무게를 갖는 트럭은 없기 때문이다) 또한 좀 더 나아가 코드적으로 봤을때 빈 큐에서 비교할 대상을 꺼낼 수 없기 때문에 NULL과 관련된 에러가 뜰 것이라 생각했기 때문이다. 

 

 

 

다음으로는 두번째 경우인, 트럭이 다리에 진입할 때이다. 트럭은 조건에 맞으면 다리에 진입하고 조건에 맞지 않으면 다리에 진입할수 없는 경우로 나뉘어진다. 처음으로 다리에 진입 불가능한 경우를 생각해보면 비교해야할 것은 이론상 총 두가지이다. 가장 먼저 다리에 트럭이 진입할 수 있는 공간이 있는지와 다리가 수용가능한 무게보다 트럭들의 무게 합이 낮은지다. 두 가지의 조건을 모두 만족해야 다리에 진입할 수 있다.

 

그림은 예시의 1초 ~ 3초의 상황으로 1초에 무게 7인 트럭이 다리에 진입했다. 그 후 1초가 지나 무게 4인 트럭이 다리에 진입하려 했으나 다리 위에 있는 트럭과 진입하려는 트럭의 무게의 합이 총 11이므로 수용 가능한 무게 10을 넘어버렸기에 진입이 불가능하다. 또 1초가 지나 무게 7인 트럭이 다리를 건너고 나서야 무게가 4인 트럭이 다리에 진입했다. 이 예시에서는 무게가 만족되지 않아 진입이 불가능했다.

 

예시에서는 다리의 공간이 없어 진입이 불가능한 경우는 보여주지 않는다. 그래서 해당 조건이 고려돼야 하는 사항인가 고민을 해보니 어찌됐든 모든 트럭이 진입 조건에 맞아 제 순서에 맞춰 진입했다해도 모든 트럭은 1초 마다 앞으로 이동하니 매 초마다 다음 트럭이 들어올 공간이 생기므로 공간이 없어 진입이 불가능한 경우가 생기나 싶었다. 그래서 조건에서 해당 부분은 삭제했다. 

 

 

다음으로는 다리에 진입 가능한 경우이다. 위에서 다리에 공간이 있는지의 조건은 빼기로 했으니 다리위의 트럭들의 무게들과 진입하려는 트럭의 무게의 합이 다리의 수용 가능한 무게보다 낮은지만 확인하면 된다. 그림은 예시의 3초 ~ 4초에 해당하는 그림이다. 무게 4의 트럭이 3초에 진입하였다. 사실 4초의 위치가 그 위로 가야 정확하지만..ㅎ 만들때 헷갈렸나보다😂 아무튼 다음으로 4초가 되었을때 무게 4의 트럭이 1만큼 앞으로 이동하고 다음으로 무게 5의 트럭이 다리에 진입하려 한다. 두개의 트럭의 무게의 합은 9이므로 다리의 수용 가능한 무게 10보다 작으므로 무게 5의 트럭은 다리에 진입이 가능하다.  

 

마지막으로는 3번째 다리를 건너 다리에서 벗어났을 때다. 모든 트럭은 1초마다 앞으로 1씩만큼 나가는데 몇초가 지나야 다리를 건널 수 있을까? 결국 다리의 길이 = 트럭이 다리를 모두 건너는데 걸리는 시간이다. 매초 트럭은 1씩 앞으로 나아가고 다리의 길이만큼 전진하면 다리를 완전히 건넌게 되는 것이다. 그래서 문제에서 주어지는 다리에 올라갈 수 있는 트럭 수(bridge_length)를 위에 트럭이 진입할 때 조건에 이용하는 것이 아니라 트럭이 다리를 완전히 건너는 조건에 사용하면 될것 같았다. 

 

 

이렇게 예시를 통해서 경우를 나눠 알고리즘의 큰 틀을 세웠다. 다음으로는 좀 더 세분화해서 알고리즘에서 어떤 변수를 어떤 방식으로 쓸지 어떤 흐름으로 쓸지를 고민한다. 그림과 함께 좀 더 자세하게 설명을 해보겠다. 

 

 

문제는 결국 모든 트럭이 다리를 완전히 건너는데에 걸리는 시간을 구하는 것으로 가장 먼저 생각한 것은 들어온 순서대로 나온대로 나가는 방식인 큐를 이용해야겠다는 것이었다. (스택/큐 카테고리 문제여서 둘 중 하나에서 고민했다😂) 다음으로는 대기하고 있는 트럭이 담긴 배열 역시 큐로 옮겼다. 이유는 역시 들어온 순서대로 빠져나오기 때문에 배열로 그대로 두기보단 큐로 옮기는 것이 좀 더 편하게 계산할 수 있기 때문이었다. 다음으로는 crossing 큐에 어떤 방식으로 트럭을 넣어야 무게를 비교하고, 다리를 다 건넜는지 비교할 수 있을지를 고민하였고 그 결과 Truck이라는 객체를 생성해 거기에 다리를 건넌 시간을 나타내는 time과 트럭의 무게를 나타내는 weight 변수를 넣었다. 그래서 time은 다리를 처음 진입했을 때 1초이므로 1을 고정하고 ready 큐에서 가장 앞의 값을 가져와 Truck 객체의 weight에 넣었다. 그래서 매번 1초가 지날때마다(반복문이 한번 돌때가 1초가 도는것) 시간을 +1 하고 매번 bridge_length과 비교하여 다리를 건넜는지 확인하고   weight을 매번 비교하여 다리에 진입할 수 있는지 확인하는식으로 짜면 되겠다고 생각했다.

 

이것을 코드로 구현하면 아래와 같이 된다. 

 

3 .  전체 코드[구현]

import java.util.*;

class Truck{
	int time;
	int weight;
	public Truck (int time, int weight) {
		this.time = time;
		this.weight = weight;
	}
}

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 1;
        int sum = 0;
        
        Queue<Truck> crossing = new LinkedList<>();  // 다리를 건너는 트럭을 담는 큐
        Queue<Integer> ready = new LinkedList<>();   // 대기하는 트럭을 담는 큐 
        
        for(int i=0; i<truck_weights.length; i++) ready.offer(truck_weights[i]); 
        
        crossing.offer(new Truck(1, ready.poll()));
  
       
        while(!crossing.isEmpty()) {
        	answer ++;
        	sum = 0;
        
        	if(crossing.peek().time == bridge_length) crossing.poll(); // 트럭이 다리를 다 건넜는지 확인
        		
            	for(Truck t : crossing) t.time += 1; // + 1초
        	
        	if(!ready.isEmpty()) {
        		
        		for(Truck t : crossing) sum += t.weight;
        		
        		if(sum + ready.peek() <= weight) {
        			crossing.offer(new Truck(1, ready.poll()));	
        		}
        	}
        }

        return answer;
    }
}

 

끝~ 🤗