[프로그래머스] Lv.2 : 다리를 지나는 트럭 - 자바[Java]

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

프로그래머스

풀이

큐를 사용하여 문제를 풀었다.

다리에 올라와있는 트럭의 인덱스를 저장하는 큐를 생성한 후

트럭이 다리 끝에 도착하면 큐에서 제거하고, 특정 조건을 만족하면 새로운 트럭을 큐에 추가한다.

 

트럭의 무게는 배열로 미리 주어지며, 트릭이 다리 끝에 도착했는지를 판별하기 위해 트럭의 출발 시간을 저장하는 int형 배열 truckDepartTime을 생성한다.

int truckCnt = truck_weights.length; // 트럭 개수

Queue<Integer> q = new ArrayDeque<>(); // 다리에 올라와 있는 트럭의 인덱스를 저장
int[] truckDepartTime = new int[truckCnt]; // 각 트럭의 출발 시간 저장
        
int time = 0; // 현재 시간
int totalWeight = 0; // 다리에 올라와 있는 트럭의 총 무게
int frontTruckIdx = 0; // 다리에 올라와 있는 트럭 중 가장 앞에 있는 트럭의 인덱스
int rearTruckIdx = 0; // 다리에 올라와 있는 트럭 중 가장 뒤에 있는 트럭의 인덱스

로직

1. 첫번째 트럭을 큐에 추가하고 truckDepartTime, totalWeight, time을 변경한다. time은 2로 변경한다.

2. 큐가 빌 때까지 다음을 반복한다.

i) 트럭이 다리 끝에 도착한 경우

- 큐에서 트럭 제거

- frontTruckIdx++

- totalWeight 변경

 

ii) 트럭을 새로 추가해야할 경우(추가할 다음 트럭이 있으며, 다리에 올라간 트럭의 총 무게가 weight를 초과하지 않고, 큐의 사이즈가 bridge_length 미만인 경우)

- rearTruckIdx++

- 큐에 트럭 추가

- 새로 추가한 트럭의 truckDepartTime을 time으로 변경

- totalWeight 변경

 

iii) time++

 

3. time-1을 반환한다.

코드

import java.util.*;

class Solution {
    
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int truckCnt = truck_weights.length; // 트럭 개수
        
        Queue<Integer> q = new ArrayDeque<>(); // 다리에 올라와 있는 트럭의 인덱스를 저장
        int[] truckDepartTime = new int[truckCnt]; // 각 트럭의 출발 시간 저장
        
        int time = 0; // 현재 시간
        int totalWeight = 0; // 다리에 올라와 있는 트럭의 총 무게
        int frontTruckIdx = 0; // 다리에 올라와 있는 트럭 중 가장 앞에 있는 트럭의 인덱스
        int rearTruckIdx = 0; // 다리에 올라와 있는 트럭 중 가장 뒤에 있는 트럭의 인덱스
        
        // 첫번째 트럭 출발
        q.add(0);
        truckDepartTime[0] = 1;
        time = 2; // 2초부터 다음 로직 시작
        totalWeight += truck_weights[0];
        
        while (!q.isEmpty()) {
            // 다리 끝에 도착한 트럭 제거
            if (truckDepartTime[frontTruckIdx] + bridge_length <=  time) {
                q.poll();
                totalWeight -= truck_weights[frontTruckIdx];
                frontTruckIdx++;
            }
            // 새로운 트럭 추가
            if (rearTruckIdx+1 < truckCnt && totalWeight + truck_weights[rearTruckIdx+1] <= weight && bridge_length > q.size()) {
                rearTruckIdx++;
                q.add(rearTruckIdx);
                truckDepartTime[rearTruckIdx] = time;
                totalWeight += truck_weights[rearTruckIdx];
            }
            time++;
        }
        
        return time - 1;
    }
}