[TIL] 프로그래머스) 42583 - 다리를 지나는 트럭 풀이 (Java), 개인 과제 제출

 > 개인 과제 제출 전 마지막 테스팅 및 스크립트 점검을 진행하고, EC2 서버 세팅 후 프로젝트를 업로드한 뒤 README 작성 및 API 명세서 작성에 집중했다. 강의를 따로 듣지는 않아서 오전 중에 풀었던 코드 카타 문제 풀이를 작성해보았다.

 

학습 키워드: Java, Queue, LinkedList

 

42583 - 다리를 지나는 트럭

1) 문제 설명 요약 (원문은 하단 링크 참고):

 요약: 다리의 길이 bridge_length, 다리의 하중 weight, 그리고 배열 truck_weights 안에 다리를 지나게 될 트럭들의 무게가 주어진다. 트럭 하나가 다리를 건너는데 걸리는 시간은 다리의 길이와 같다. 다리의 하중이 허용하는 한 여러 대의 트럭이 순차적으로 다리에 진입하여 통과할 수 있다. 이 때, 모든 트럭이 다리를 지나는데 걸리는 시간을 구하는 문제다.

 조건: 1 <= bridge_length <= 1000, 1 <= 모든 트럭의 무게 <= weights <= 10000, 1 <= truck_weights.length <= 10000

 

 

2) 예전에 작성한 코드 (LinkedList):

import java.util.LinkedList;
class Solution {
    private class Truck {
        int w, t;
        Truck (int w, int t) {
            this.w = w;
            this.t = t;
        }
    }
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int cur_weight = 0, t = 1;
        LinkedList<Truck> queue = new LinkedList<Truck>();
        for (int w : truck_weights) {
        	cur_weight += w;
        	while (queue.size() == bridge_length || (!queue.isEmpty() && cur_weight > weight)) {
    			Truck truck = queue.poll();
    			cur_weight -= truck.w;
    			if (truck.t + bridge_length > t) t = truck.t + bridge_length;
    		}
            queue.offer(new Truck(w, t++));
        }
        
        return queue.pollLast().t + bridge_length;
    }
}

 채점 결과:

 몇 년 전에 한 번 풀어봤던 문제여서 코드 기록이 남아있었다. LinkedList (Java에서 Queue 기능을 함)와 커스텀 class를 이용하는 정석적인 방식이다. 새로운 트럭이 다리 위로 올라갈 때 마다 이 트럭이 다리를 완전히 통과할 때의 시간을 미리 계산하여 트럭의 무게와 함께 Truck 객체를 생성한 뒤 객체를 Queue에 넣어주고, 다리의 하중이 가득차면 Queue를 pop 하면서 새로운 트럭이 들어갈 자리를 만들어주면서 동시에 pop 된 트럭들을 통해 경과된 시간을 갱신하는 방식이다. 동작 시간이 막 엄청 길지는 않은데, 더 빠르게 만들 수 있을 것 같아서 초기화하고 새롭게 풀어보기로 했다.

 

 

3) Array만 이용한 풀이 (정답):

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int[] passesAt = new int[truck_weights.length]; // #1
        int passingIdx = 0;
        int onBridgeWeight = 0;
        int time = 0;
        for (int i = 0; i < truck_weights.length; i++) {
            time++;
            int curWeight = truck_weights[i];
            if (onBridgeWeight + curWeight > weight) {
                while (passingIdx < i) {
                    onBridgeWeight -= truck_weights[passingIdx++];
                    if (onBridgeWeight + curWeight <= weight) break;
                }
                int passedAt = passesAt[passingIdx - 1];
                if (passedAt > time) time = passedAt; // #2
            }
            passesAt[i] = time + bridge_length;
            onBridgeWeight += curWeight;
        }
        return passesAt[passesAt.length - 1]; // #3
    }
}

 채점 결과:

 Queue 같은 자료 구조를 사용할 때마다 항상 따라오는 문제는 pop()과 offer() 등 자료를 조작하는 method의 호출로 메모리 영역 할당이 잦아서 동작 시간이 느리게 나온다는 점이다. 새롭게 작성한 코드는 Queue 대신 passesAt 이라는 int 배열을 생성하여 미리 사용할 양 만큼의 메모리 공간을 할당 해두도록 구현했다.

 

 Queue를 모방하기 위해 루프의 바깥에 passingIdx 라고하는 index 값을 하나 두고, 루프를 돌면서 passesAt의 index마다 트럭이 다리를 빠져나가게 될 때의 시간(현재 경과 시간 + 다리의 길이)을 계산하여 기록해준다. 다리의 하중이 초과되면 다리에 새로운 트럭을 위한 하중의 여유가 생길 때 까지 passesAt을 passingIdx에서 부터 iterate한다. 여유 공간이 생기는 시점에서 while 루프를 break하고, (중요) 현재 시간과 마지막으로 빠져나간 truck의 탈출 시각을 대조하여 더 큰 값에 맞춰 경과 시간을 갱신해줘야 한다.

 

 바깥 for 루프가 완료되면 passesAt 배열의 맨 끝 항목에 들어있는 값이 마지막 트럭이 지나간 시간이므로 이를 return 하면 된다.

 

 다 풀고나서 예전 기록도 살펴봤는데, 이번과 마찬가지로 위에 (중요)라고 표시해 둔 부분을 구현하지 않아서 71점을 받았었다. 다리에 새로 트럭이 올라오기 위해서 먼저 진입한 트럭들을 내보냈을 때, 트럭이 탈출한 시간 이후에 새로운 트럭이 올라오게 된다는 점을 간과하고 ++된 경과 시간만 사용한 것이 문제였다.

 

 이전과 같은 포인트에서 발목이 잡힌 부분은 아쉽지만, 성능을 향상시킬 수 있었다는 점에서 만족스러운 문제였다.