반응형
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 |