알고리즘 문제풀이 [#3] 다리를 지나는 트럭

이미 해답지가 인터넷에 다 있어 저도 올리지만,

이미 다 풀어주신 분만 밑으로 봐주시길 바랍니다.

 

문제 설명 이후에 답안 나옵니당.

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

코딩테스트 연습 - 다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

이런 문제였습니다.

 

요즘에 아는 (신입시절을 제 옆자리로 오신;;) 지인개발자가 알고리즘문제를 열심히 풀고 있어서. .

옆에서 먼저 풀어보고 던진다음에 제 코드는 이렇습니다 하고서

경력낮은 개발자분에게 폼잡는 ... 브론즈티어에게 폼잡는 골드티어랄까요 ㅋ

 

아무튼 옆자리였던 분이 읽을 것을 가정하고,

조금 친절하게 사고의 흐름을 적어볼까 합니다.

 

이 밑으로는 풀이과정이 나옵니다. 조심.. 

 

 

 

 

 

 

 

이 문제가 스택/큐 카테고리에 있어서 대부분 스택/큐로 풀으셨던데 그냥 맵으로 풀었습니다(-ㅅ-)a 
(찬양하라 SI에서부터 널리 쓰이는 맵이여..)

아참 각 변수에 대한 제한조건은 적진 않았습니다.

목적이 문제풀이 정답 100점부터 맞는거다보니..

 

 

 

 

 

 

 

 

 

 

문제의 인식

이런 문제를 만나면 종이에 적고 푸는 지라. . 제가 적었던 종이사진을 공유합니다.

우선 동작하는 기능의 구현을 잘 할려면 국어를 잘해야 한다고 합니다. 

다리가 원하는 기능을 종이에 적어봅니다.

 

우선 1번의 그림을 그리고 이런저런 기능과 필요한 사항들을 적어봅니다.

 

1) 다리는 여러 트럭들이 올라와져있다

2) 현재 올라와진 차들의 무게를 구할 수 있어야 한다. 

3) 올라올 때 차량 무게가 기록되고 나갈때 다리의 현재 보유 무게가 바귄다.

2) 자료구조의 고민

번의 그림을 그리고.. 이전 알고리즘의 시험에서 무슨 어떤 노드 시스템? 같은 것을 봐서.. 한번 노드를 그려봅니다. 

다리의 한칸한칸..을 그려야하나..? 이것이 바로 스택/큐 관련 코딩인가(- _-?) 라는 궁금증을 가져봅니다.

잠시 스택큐 구글링도 해봅니다.

잠시 머리속에 차량 한칸한칸을 가지고 있다가 옆으로 미는 모습을 생각합니다. 머리속이 복잡해집니다.

 

3) 이벤트의 고민

뭔가 문제를 발견하면 여기에 맞는 문법, 형태에 고민하다가 더 복잡해지는 경우가 은근 있어서

다른 방법을 고민해봅니다.

1번에서 제일 밑에 적었던, 여러 복잡한 변수들을 가장 축소화해서

1초부터 오직 차량한대만 가지고 일어나는 이벤트들에 대하여 생각을 해봅니다.

 

가장 첫번째 트럭이 1초에 다리에 진입(enter) 합니다.

그리고 3초에 빠져나가게(leave) 됩니다.

다리의 무게는 0 -> 7 이 되면서 그 뒤의 트럭들이 들어올 수 있는지 묻겠지만( can accept ?)

받을 수 없습니다. 

머리속에 뭔가 돈 현금출납 장부가 떠오릅니다. ( 돈은 잘 기억하자 으으 ㅠ) 

이렇게 생각을 해보니 맵이 떠오릅니다.  (오오 맵이시여... ㅋ)

1초에 7이 들어오지만 다리길이 2가 추가되서 3초에는 이 자동차는 나갈 것이다.

3초에 7이 나가면서 4가 가 들어오지만 물론 이 4도 다리길이 2가 추가되서 5초에는 나갈 것이다. 

 

이런 식의 흐름이 그려집니다. 뭔가 될 것같습니다.

 

다리에서 벌어지는 일들을 그려봅니다.

 

다리가 하는 일 혹은 벌어지는 일..

1) 시간을 +1 초 시킨다 (plus time)

2) 차량을 내보낸다  ( leave )

3) 차량을 내보내면서 들어올 수 있는 차량이 있는지 묻는다. ( canAccept ? )

4) 들어올 수 있다면 받는다. ( accept )

 

먼저 브릿지 클래스를 만듭니다. 

현재 하중은 0으로 시작해서 차가 들락날락 하면서 바뀔 예정입니다.

맵으로 내보낼 시간을 키로 간직하고 빠질 무게를 간직하는 맵이 있습니다.

 static class Bridge {
        // 길이
        final private int length;
        // 한계 하중
        final private int weight;
        // 시간 모델
        private int second = 1;
        // 현재 하중
        private int currentWeight = 0;
        // 트럭 장부
        final private Map<Integer, Integer> jangbu = new HashMap<>();

        public Bridge(int length, int weight) {
            this.length = length;
            this.weight = weight;
        }
}

시간의 증가를 구현합니다. 

시간이 증가가되면서 차량도 자동적으로 내보지게됩니다.

/**
         * 트럭다리의 시간을 1초 흐르게 한다.
         */
        public void plusTime() {
            System.out.println(toString());
            second++;
            leaveTruckIfPossible();
        }

        /**
         * 현재 이벤트 시간에 기록된
         * 트럭나갈 기록이 있는지 묻는다.
         */
        private void leaveTruckIfPossible() {
            if (jangbu.get(second) != null) {
                currentWeight -= jangbu.get(second);
                System.out.println("현재 시간 "+second+",  나간 truck :"+jangbu.get(second));
                jangbu.remove(second);
            }
        }

현재 차량이 들어와도 되는지 묻는 로직은 

현재 하중 + 들어올 트럭하중 <= 다리 하중이긴한데

currentWeight + truckWeight <= weight

생각해보니 물으면서 차를 받을 것없이 그냥 차량을 받을 수 있을때까지 계속 받으면 되더라구요.. 

 

현재 차를 받을 수 있으면 차를 현재 하중에 추가시키고, 

장부에 기록하고 시간을 올리고

지금 차를 못받으면 시간을 올리고 다시 받을 수 있냐 물어보면 됩니다.  못받으면 다시 시간 올리고 받을 수 있어? 어 그래도 못 받어?! 그럼 다시 시간을 올리고( ... )

public void accept(int truckWeight) {
            if (currentWeight + truckWeight <= weight) {
                currentWeight += truckWeight;
                jangbu.put(second + length, truckWeight);
                plusTime();
            } else {
                plusTime();
                accept(truckWeight);
            }
        }

( 대략.. 차들어갈때까지 입벌리세요 느낌.. 아아 정신이 아득해진다... )

 

총 코드는 이렇게 나오게 되고... 

/**
     * 다리가 하는 일
     * 1) 가장 먼저 시간을 +1 초 시킨다
     * 2) 차량을 내보낸다
     * 3) 들어올 수 있는 차량이 있는지 묻는다.
     * 4) 들어올 수 있다면 받는다.
     */
    static class Bridge {
        // 길이
        final private int length;
        // 한계 하중
        final private int weight;
        // 시간 모델
        private int second = 1;
        // 현재 하중
        private int currentWeight = 0;
        // 트럭 장부
        final private Map<Integer, Integer> jangbu = new HashMap<>();

        public Bridge(int length, int weight) {
            this.length = length;
            this.weight = weight;
        }

        /**
         * 새로 트럭을 받는다. ( 하중을 올리고 이벤트 기록 )
         */
        public void accept(int truckWeight) {
            if (currentWeight + truckWeight <= weight) {
                System.out.println("truck :"+truckWeight+" , "+second+"초 에 입장합니다.");
                currentWeight += truckWeight;
                jangbu.put(second + length, truckWeight);
                plusTime();
            } else {
                plusTime();
                accept(truckWeight);
            }
        }

        /**
         * 트럭다리의 시간을 1초 흐르게 한다.
         */
        public void plusTime() {
            System.out.println(toString());
            second++;
            leaveTruckIfPossible();
        }

        /**
         * 현재 이벤트 시간에 기록된
         * 트럭나갈 기록이 있는지 묻는다.
         */
        private void leaveTruckIfPossible() {
            if (jangbu.get(second) != null) {
                currentWeight -= jangbu.get(second);
                System.out.println("현재 시간 "+second+",  나간 truck :"+jangbu.get(second));
                jangbu.remove(second);
            }
        }

        // 최종 시간 알기
        public int getSecond() {
            return second;
        }

        public boolean hasTruck(){
            return currentWeight != 0;
        }

        @Override
        public String toString() {
            return "다리의 현재 시간 :"+second+", 현재 무게 :"+currentWeight+", 차량장부 :"+jangbu;
        }
    }

    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Bridge bridge = new Bridge(bridge_length, weight);
        for(int truck : truck_weights){
            System.out.println("truck :"+truck+" 입장 여부 묻는 중");
            bridge.accept(truck);
        }
        // 마지막 트럭이 있다면 비워라
        while(bridge.hasTruck()){
            System.out.println("마지막 트럭 처리 중입니다.");
            bridge.plusTime();
        }
        return bridge.getSecond();
    }

 

솔루션 코드는 이렇게 되죠.. 

 

트럭배열에서 하나씩 트럭들을 브릿지에 accept 수락시키고

브릿지에 트럭이 있는 동안에는 시간을 흘려보내 브릿지를 비우게하고

시간을 얻으면 됩니다 ?

public int solution(int bridge_length, int weight, int[] truck_weights) {
        Bridge bridge = new Bridge(bridge_length, weight);
        for(int truck : truck_weights){
            System.out.println("truck :"+truck+" 입장 여부 묻는 중");
            bridge.accept(truck);
        }
        // 마지막 트럭이 있다면 비워라
        while(bridge.hasTruck()){
            System.out.println("마지막 트럭 처리 중입니다.");
            bridge.plusTime();
        }
        return bridge.getSecond();
    }

그럼 결과는 대략 이렇게 됩니다. 

 

 

그럼 개발자에게 궁금한 건.. 남이 어떻게 했나 궁금하니 한번 살펴봅니다.

따봉 제일 많은거 두개 보고 오늘은 이만..

 

class Solution {
    class Truck {
        int weight;
        int move;

        public Truck(int weight) {
            this.weight = weight;
            this.move = 1;
        }

        public void moving() {
            move++;
        }
    }

    public int solution(int bridgeLength, int weight, int[] truckWeights) {
        Queue<Truck> waitQ = new LinkedList<>();
        Queue<Truck> moveQ = new LinkedList<>();

        for (int t : truckWeights) {
            waitQ.offer(new Truck(t));
        }

        int answer = 0;
        int curWeight = 0;

        while (!waitQ.isEmpty() || !moveQ.isEmpty()) {
            answer++;

            if (moveQ.isEmpty()) {
                Truck t = waitQ.poll();
                curWeight += t.weight;
                moveQ.offer(t);
                continue;
            }

            for (Truck t : moveQ) {
                t.moving();
            }

            if (moveQ.peek().move > bridgeLength) {
                Truck t = moveQ.poll();
                curWeight -= t.weight;
            }

            if (!waitQ.isEmpty() && curWeight + waitQ.peek().weight <= weight) {
                Truck t = waitQ.poll();
                curWeight += t.weight;
                moveQ.offer(t);
            }
        }

        return answer;
    }
}

(큐를 안 쓴 나는.. ㅠ 흑 )

 

두번째 따봉많은 답변인데 브릿지맵이 비슷한.. 듯?

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
            Stack<Integer> truckStack = new Stack<>();
            Map<Integer, Integer> bridgeMap = new HashMap<>();

            for (int i = truck_weights.length-1; i >= 0; i--)
                truckStack.push(truck_weights[i]);

            int answer = 0;
            int sum = 0;
            while(true) {
                answer++;

                if (bridgeMap.containsKey(answer))
                    bridgeMap.remove(answer);

                sum = bridgeMap.values().stream().mapToInt(Number::intValue).sum();

                if (!truckStack.isEmpty())
                    if (sum + truckStack.peek() <= weight)
                        bridgeMap.put(answer + bridge_length, truckStack.pop());

                if (bridgeMap.isEmpty() && truckStack.isEmpty())
                    break;


            }
            return answer;
    }
}

 

 

======

세상에 나쁜 코드는 없다.

친절히 코드로 이야기하려합니다 by 아라한사