Today's Algorithm(2018-10-26)

programmers 다리를 지나는 트럭

어제 세탁이 끝나기를 기다리며 읽어봤던 문제인데요. 처음엔 쉽다고 생각했습니다. 그 때는 고려해야할 변수들이 많이 안 보였거든요. 근데 막상 구현을 하려니 생각보다 변수들이 많더라구요.

현재 다리 무게, 대기 트럭, 다리 위의 트럭, 경과 시간

그래서 문제를 풀다가 이것저것 추가하다보니 되게 지저분해진 것 같아요. 다른 사람들은 어떻게 풀었는지 궁금하네요. 우선 제가 풀었던 방식을 코드로 살펴볼께요.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> before = new LinkedList();
        LinkedList<Integer> middle = new LinkedList<>();
        int answer = 0;  // 경과 시간
        int curWeight = 0;  // 다리 무게
        int truckIndex = 0;  // 트럭 무게 알기위함

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

        while (true) {
            answer++;

            // 거리 증감부터 하는 이유는 트럭 추가 후 바로 거리 증가를 막기위함
            if (!middle.isEmpty()) {
                for (int i = 0; i < middle.size(); i++) {
                    middle.set(i, middle.get(i) + 1);  // 다리 위 트럭 모두 거리 +1 증가
                }

                // 모두 증가시키고 이후에 비교하여야함. 안 그러면 poll() 때문에 인덱스 변경 발생
                if (middle.getFirst() == bridge_length) {
                    middle.poll();
                    curWeight -= truck_weights[truckIndex];
                    truckIndex++;  // 트럭이 들어온 순서대로 빠지기 때문에 차례로 인덱스 늘려주면 됨
                }
            }

            // 트럭 추가
            if (!before.isEmpty() && curWeight + before.peek() <= weight) {
                curWeight += before.poll();
                middle.offer(0);  // 트럭 다리 위에 추가시 거리 0으로 추가
            }

            if (middle.isEmpty()) {  // 다리 위에 트럭 아무것도 없을 때 종료
                break;
            }
        }

        return answer;
    }
}

 

다른 사람들도 Queue를 이용하여 다양한 방식으로 푸셨더라구요. 그리고 많은 분들이 객체지향적으로 Truck이라는 클래스를 생성하고 moving() 매서드를 이용하여 푸셨더라구요. 물론 객체지향을 제대로 구현하는 것은 어렵지만 사람의 생각과 비슷한 구조라 확실히 코드가 눈에 잘 보이고 상태값도 명확하게 잘 보이는 것 같아요. 뭐 경시대회라면 모르겠지만 입사테스트까지는 이렇게 설계하는 것도 괜찮지 않을까요?