알고리즘 공부 3일 차(다리를 지나는 트럭)

시작

알고리즘 3일 차
늘 그렇듯이 문제를 해석하는게 일이지만 다행이도 해석하는게 어렵지는 않았다.

문제인식

1. bridge_length는 다리의 길이이다.
2. 모든 트럭은 다리를 지나는데 다리 길이 +1 만큼 걸린다.(bridge_length만큼 칸이 있다고 생각하면 편하다.)
   bridge_length가 2라면 2칸이 있고 다리를 지나는데 3초가 걸린다.
   bridge_length가 100이라면 다리를 지나는데 101초가 걸린다
3. truck_weights는 weight보다 작아야 한다.
4. truck_weights의 합이 weight보다 작으면 동시에 올릴 수 있다.

예시

bridge_length=2, weight=10, truck_weight=[7, 4, 5, 6]
bridge_length가 2이므로 다리는 2칸이다.
weight가 10이므로 다리가 버틸 수 있는 최대 무게는 10이다.

문제 해결

문제를 이해했으니 문제를 해결해 보자
다음은 내가 참고한 블로그이다. https://minhamina.tistory.com/241

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++) {
			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  {
					if(sum + truck <= weight) {
						queue.add(truck);
						sum += truck;
						time++;
						break;
					} else { 
						queue.add(0);
						time++;
					}
				}
			}
		}
		return time + bridge_length; 
    }
}

코드 해석

내가 해석한 내용이다.

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> queue = new LinkedList<>();
		int sum = 0;
		int time = 0; 

int bridge_length, int weight, int truck_weights 리스트를 받는다.
queue라는 이름의 queue 리스트를 만든다.
int sum, int time은 0이다.

for(int i = 0; i < truck_weights.length; i++) {
			int truck = truck_weights[i];

i는 0이고 truck_weights의 길이보다 i보다 작거나 같을 때까지 i는 1씩 증가한다.(for)
truck은 truck_weights의 리스트들이다.

while(true) {
				if(queue.isEmpty()) { 
					queue.add(truck);
					sum += truck;
					time++;
					break;
				} else if(queue.size() == bridge_length) {
					sum -= queue.poll();
				} else  {
					if(sum + truck <= weight) {
						queue.add(truck);
						sum += truck;
						time++;
						break;
					} else { 
						queue.add(0);
						time++;
					}
				}
			}

문장을 무한 반복한다.(while)
만약 queue가 비어있다면
    queue에 트럭을 올려준다.
    sum에 truck무게를 추가한다.
    time에 +1을 한다.
    while문을 나간다.
또는 queue의 사이즈와 다리의 길이가 같다면
    sum에서 queue의 맨 앞 데이터를 제거한다.
그 외에는
    만약 sum과 truck의 합이 weight보다 작거나 같으면
         queue에 truck을 올린다.
         sum에 truck무게를 추가한다.
         time에 1을 추가한다.
         while문을 나간다.
    그 외에는
         queue에 빈칸을 올린다.
         time에 1을 추가한다.

return time + bridge_length;

time(지금까지 걸린 시간)과 bridge_length(마지막 트럭이 건너는데 걸리는 시간)를 합친 값을 반환해준다.

소감

재밌다