[고득점 kit] 다리를 지나는 트럭

난이도 중

화낼거양

Mar 21, 2025

Contents

정답

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

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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

기본적으로 주어진 코드 :


class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        return answer;
    }
}

정답


class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        // bridge_length의 값과 동일한 길이의 배열을 생성
        int[] bridgeLengthArr = new int[bridge_length];
        // 배열을 -1로 모두 초기화
        for (int i = 0; i < bridgeLengthArr.length; i++) {
        	bridgeLengthArr[i] = -1;
        }
        // 다리위에 트럭이 올라가면 값 증가, 트럭이 빠져나가면 값이 하락되는 변수
        int bridgeOnWeight = 0;
        int count = 0; // 한번 순회할 때 마다 1씩 증가. (반환값)
        boolean complete = false; // 마지막 트럭까지 다리에 올라갔을 때 true로 변경
        
        // 계산시작
        for (int i = 0; i < truck_weights.length; i++) {
        	count++;
        	// 다리 위에 있는 인덱스들을 -1 만큼 순회하면서 옮김 (마지막 인덱스 제외)
        	for (int j = 0; j < bridgeLengthArr.length - 1; j++) {
    			if (j == 0) {
    				// 인덱스가 0이면서 -1이 아니라면 트럭이 내리기 직전이라는 뜻
    				if (bridgeLengthArr[0] != -1) {
    					// 트럭이 다리에서 빠져나가기 때문에 bridgeOnWeight 값을 트럭 무게만큼 하락
    					bridgeOnWeight -= bridgeLengthArr[0];
    				}
    				// 0번째 인덱스를 1번째 인덱스 값으로 변경
    				bridgeLengthArr[0] = bridgeLengthArr[1];
    			} else {
    				// 그렇지 않다면 배열[인덱스] 값을 인덱스 +1 값으로 변경
    				bridgeLengthArr[j] = bridgeLengthArr[j + 1];
    			}
    		}
        	// 위 내용은 마지막 인덱스를 건드리지 않고 있기 때문에, 모든 트럭이 다리에 올라간 경우. 마지막 인덱스를 -1로 수동변경해주어야 한다.
        	if (complete) { bridgeLengthArr[bridgeLengthArr.length -1] = -1; };
        	
        	// 아직 모든 트럭이 다리에 올라가지 않은 상태일 때
        	if (!complete) {
        		// 아직 마지막 인덱스는 손대지 않은 상태
            	// 다리위에 다음 트럭을 올릴 수 있다면
            	if (bridgeOnWeight + truck_weights[i] <= weight) { 
            		// 마지막 인덱스에 트럭을 올린다.
            		bridgeLengthArr[bridgeLengthArr.length - 1] = truck_weights[i];
            		// 트럭이 올라갔으니 무게도 올린다.
            		bridgeOnWeight += truck_weights[i];
            		// 마지막 인덱스 트럭이 올라갔다면 complete를 true로 변경한다.
            		if (i == truck_weights.length - 1) {
            			complete = true;
            		}
            	} else {
            		// 그렇지 않다면 마지막 인덱스에 -1을 대입한다.
            		bridgeLengthArr[bridgeLengthArr.length - 1] = -1;
            		// 트럭을 올리지 않았으니 i값을 증가시키면 안된다.
            		i--;
            	}
        	}
        	// 모든 트럭이 다리에 올라갔을 때 
        	if (complete) {
        		for (int j = 0; j < bridgeLengthArr.length; j++) {
            		// 다리위에 트럭이 아직 남아 있다면 추가 반복을 위해 i를 감소
        			if (bridgeLengthArr[j] != -1) {
            			i--;
            			break;
            		}
            	}
        	}
        }
        return count;
    }
}

코드 설명은 주석을 참고