Google 태그 관리자 아이콘

알고리즘 풀이

.programmers(다리를 지나는 트럭)

silvergoni 2022. 4. 8. 17:01
반응형

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

 

1. 2022.04.08 시도

소요시간: 45분

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int timer = 0;
        int sum_of_truck_weight = 0;
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> timerMapByTruck = new HashMap<>();
        for (int truckIndex=0; truckIndex<truck_weights.length; truckIndex++) {
            while (sum_of_truck_weight+truck_weights[truckIndex] > weight) {
                int firstTruckIndex = queue.poll();
                int elapsed = timerMapByTruck.get(firstTruckIndex);
                int remain = bridge_length - elapsed < 0 ? 0 : bridge_length - elapsed;
                timerMapByTruck.remove(firstTruckIndex);
                sum_of_truck_weight-=truck_weights[firstTruckIndex];
                
                for (Integer eachTruck: timerMapByTruck.keySet()) {
                    timerMapByTruck.put(eachTruck, timerMapByTruck.get(eachTruck) + remain);
                }
                timer += remain;
            }
                
            sum_of_truck_weight += truck_weights[truckIndex];
            queue.offer(truckIndex);
            timerMapByTruck.put(truckIndex, 0);
            for (Integer eachTruck: timerMapByTruck.keySet()) {
                timerMapByTruck.put(eachTruck, timerMapByTruck.get(eachTruck) + 1);
            }
            timer++;
        }
        timer+=bridge_length;
        
        return timer;
    }
}

풀이 접근 과정

다리 무게가 견딜 수 있다면 트럭을 queue에 추가하고 그것들의 각각의 경과 시간을 map에 기록해둔다.

전체 timer도 하나 기록해 둔다.

만약 다리 무게를 견딜 수 없다면 이전에 건너고 있던 트럭들이 보낸다.
이전 트럭들을 언제까지 보내느냐는, 다음에 올 트럭이 건널 수 있을 때까지이다.(while문 조건)
그리고 트럭들이 지나간 시간들을 다른 트럭의 경과시간과 전체 타이머에도 더해준다.

마지막 차가 다리에 진입하면 for문이 끝난다.
따라서 마지막 차가 다리를 빠져나가는 시간인(bridge_length)를 전체 타이머에 더해준다.

 

느낀점

  • 역시 프로그래머스 문제는 복잡하다. 뭔가 하나라도 삐끗하면 대혼란이 있을 수 있는 문제다. 정말 조심조심 풀어가야한다.
  • 이 풀이가 가장 깔끔한건 아니어도 가장 빠른 시간 복잡도로 실행되는 풀이 중 하나는 맞을거다.

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형

 

'알고리즘 풀이' 카테고리의 다른 글

.programmers(더 맵게)  (0) 2022.04.08
.programmers(주식가격)  (0) 2022.04.08
.leetcode(347. Top K Frequent Elements)  (0) 2022.04.08
.programmers(프린터)  (0) 2022.04.08
.programmers(기능개발)  (0) 2022.04.08