[알고리즘/Programmers] LV2. 다리를 지나는 트럭 (Java)

 

 

오늘의 학습 키워드

• 큐

오늘의 회고

1. 문제

문제 URL

프로그래머스

2. 해결 방안

import java.util.*;

/** 42583
 * 코딩테스트 연습 > 스택/큐 > 다리를 지나는 트럭
 */
public class test_42583 {

    public static void main(String[] args) {
        int[] truck_weight = {7,4,5,6};
        System.out.println(solution(2, 10, truck_weight));
    }

    /**
     * 모든 트럭이 다리 건널 때 최소 몇초가 걸리냐
     * 트럭은 최대 bridge_length대 올라감
     * weight 이하 무게 견딜 수 있음
     *
     */
    public static int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        int totalWeight = 0;
        Queue<Integer> bridgeQueue = new LinkedList<>(); // 다리 위의 트럭 상태를 저장하는 큐

        // 다리를 빈 공간으로 초기화
        for(int i=0; i<bridge_length; i++) {
            bridgeQueue.add(0);
        }

        for (int truck : truck_weights) {
			while (true) {
                totalWeight -= bridgeQueue.poll(); // 다리에서 트럭을 하나 빼고

                time++; // 시간 증가

                if (totalWeight + truck <= weight) { // 새로운 트럭을 올릴 수 있으면
                    bridgeQueue.add(truck); // 다리에 트럭 추가
                    totalWeight += truck; // 다리 위의 무게 갱신
                    break;
                } else {
                    bridgeQueue.add(0); // 다리에 빈 공간 추가
                }
            }
        }

        // 모든 트럭이 다리를 건넜으므로 마지막 트럭이 다리를 완전히 건너는 시간을 더해줌
        time += bridge_length;
        return time;
    }
}

• 다리를 큐라고 생각하고 트럭이 들어오고 나가는 것을 관리한다.
• 처음엔 다리를 다리 길이 만큼 0으로 초기화하고, 하나씩 빼면서 time을 증가한다.
• 다리에서 트럭을 빼거나 추가할 때 totalWeight 변수에 트럭 무게를 증감한다.
• 마지막 리턴 시, 모든 트럭이 다리를 건넜으므로 마지막 트럭이 다리를 완전히 건너는 시간(=다리 길이)를 더해준다.

3. 피드백

• 처음에 통과 못했던 이유
  • 문제 잘못 이해함. 대기 트럭 지정된 순서대로 이동하는게 아니고 빠르게 통과할 수 있는 기준으로 이동해도 되는 줄 알았음.
  • 제출 시간 초과. 조건 확인 시 다리에 있는 트럭의 총 무게가 필요한데 덧뺄셈으로 관리할 수 있었던 것을 매번 큐에 있는 전체 트럭 무게를 계산했음.
  • 대기 트럭도 큐로 두고 하나씩 빼면서 짰는데, 가장 밖에 for문을 두고 대기 트럭이 끝까지 빠져나갈 수 있도록 코드를 짜면 되었음.
• 다른 사람 풀이 방식을 보며 힌트를 얻고 위 코드로 변경하여 문제 해결함.