반응형
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
나의 풀이 (java)
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int seconds = 0;
int truckIndex = 0;
int passingWeights = 0;
Queue<Integer> passingTruck = new LinkedList<>();
while(truck_weights.length > truckIndex){
seconds++;
// 건너가는 트럭이 있다면 앞에서 하나씩 제거
if(passingTruck.size() == bridge_length){
passingWeights -= passingTruck.poll();
}
if(weight >= passingWeights + truck_weights[truckIndex]){
// 다리 하중이 괜찮다면, 한 대 더 건너가기
passingTruck.add(truck_weights[truckIndex]);
passingWeights += truck_weights[truckIndex];
truckIndex++;
}else{
passingTruck.add(0);
// 다라 하중이 꽉차면, 다리 위의 트럭만 1칸 건너가기
}
}
return seconds+bridge_length;
}
}
풀이 방법
- Queue의 기본 메소드 (poll,add)를 이용해 트럭을 이동시킨다 (다리 전 -> 다리 위, 다리 위 -> 다리 후)
- 적절한 조건 처리 (다리 하중)
다른사람의 풀이 (java)
mport java.util.*;
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;
}
}
Godd Idea : Java의 OOP를 활용한 풀이. 객체를 만들어서 무게&이동을 관리한다는 접근이 좋은듯.
느낀점
이번 문제는 풀이가 다양하다. 직독직해 느낌의 내 풀이도 맘에 들지만!
다른 사람들의 풀이를 보는 재미가 있는 문제였다.
풀이 방법은 결국 비슷하지만, 구현하는 방식이 다 다르다!
객체를 만들어서 OOP로 접근하거나
Map으로 제거하는 방법도 좋았다.
반응형
'개발 > 코딩 테스트' 카테고리의 다른 글
[알고리즘] 프로그래머스 > 해시 > 베스트앨범 (0) | 2022.08.10 |
---|---|
[알고리즘] 프로그래머스 > 힙 > 더 맵게 (0) | 2022.08.09 |
[알고리즘] 프로그래머스 > 스택/큐 > 프린터 (0) | 2022.08.06 |
[알고리즘] 프로그래머스 > 스택/큐 > 올바른 괄호 (0) | 2022.08.06 |
[알고리즘] 프로그래머스 > 해시 > 폰켓몬 (0) | 2022.08.06 |