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

우선 이 문제는 내가 예전에 한번 풀었었다. 하지만 최근에 다시 풀 기회가 생겨서 풀었는데 내가 제한 시간안에 풀지 못해 너무 자존심이 상해서 다시 풀고 풀이를 올린다!

 

문제

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

프로그래머스

 

 

문제 풀이

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int sum = 0;
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < truck_weights.length; i++) {
            int truck = truck_weights[i];
            while (true) {
                if (q.isEmpty()) {
                    q.add(truck);
                    sum += truck;
                    answer++;
                    break;
                } else if (q.size()==bridge_length){
                    sum -= q.remove();
                }else{
                    if((truck + sum) > weight){
                        q.add(0);
                        answer++;
                    }else{
                        q.add(truck);
                        sum += truck;
                        answer++;
                        break;
                    }
                }
            }
        }
        return answer+bridge_length;
    }
}

 

 

풀이 과정

이 문제는 Queue를 쓰면 생각보다 쉽게 풀 수 있는 문제다.

우선 다리를 Queue로 가정해서 다리를 다 통과하면 Queue에서 내보내는 방향으로 코드를 짜면 된다.

 

1.

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

우선 트럭의 갯수만큼 반복문을 실행한다.

그리고 트럭 1개의 무게를 truck이라는 변수에 저장한다.

 

2.

while (true) {
                if (q.isEmpty()) {	// - 1
                    q.add(truck);
                    sum += truck;
                    answer++;
                    break;
                } else if (q.size()==bridge_length){	// - 2
                    sum -= q.remove();
                }else{	// - 3
                    if((truck + sum) > weight){	// - 3-1
                        q.add(0);
                        answer++;
                    }else{		// - 3-2
                        q.add(truck);
                        sum += truck;
                        answer++;
                        break;
                    }
                }
            }

그리고 무한 루프를 만들어서 특정 조건이 달성되면 반복문을 탈출하게 만든다.

1. q.isEmpty() 즉, 다리가 비어있을 때는 무조건 트럭이 1대는 올라갈 수 있으니 다리(q)에 트럭을 올려주고
   총 무게(sum)에 트럭의 무게를 더해준 뒤, 시간(answer)을 1초 올려준 다음에 다음 트럭을 위해서 반복문을 탈출한다.
2. 만약 다리에 올라와 있는 트럭의 갯수가 다리의 길이와 같은 경우(q.size()==bridge_length)
   그러면 트럭을 더 이상 받지 못하기 떄문에 당연히 q.remove()로 트럭을 다리에서 빼주고 추가로 총 무게에서 트럭의 무게도 함께 빼준다.
3. 다리가 비어있지도 않고 꽉 차있지도 않은 경우
   1. 만약 추가할 트럭의 무게(truck)와 기존에 다리에 올라와 있는 트럭들의 무게(sum)이 다리가 버틸 수 있는 총 하중(weight)보다 크면 트럭을 추가하면 안되므로 임시로 다리에 무게가 0인 트럭을 추가하고 시간초는 1초를 흘러가게 한다.
   2. 트럭을 다리에 추가해도 이상이 없는 경우에는 다리에 트럭을 추가하고 총 트럭의 무게에 추가할 트럭의 무게를 추가한 뒤 시간 초를 1초 흘러가게 한다.

 

이 문제의 핵심은 트럭의 무게가 꽉 차서 더 이상 추가하지 못하고 그냥 다리에 있는 트럭들을 보내야 될 때 어떻게 처리하느냐가 핵심인 것 같은데 나는 그냥 단순히 트럭은 무조건 1초마다 들어가지만 지지하중보다 총 트럭의 무게가 초과될 경우에는 무게가 0인 트럭을 추가해서 로직에 문제가 안생기는 방향으로 알고리즘을 설계했다.