문제 해석
•
우선 직관적으로 다리에 차들이 일렬로 지나가는 모습이 그려지면서 FIFO(First In First Out)의 자료구조가 필요하다고 판단되었다.
◦
Java에서는 큐를 통해서 구현 할 수 있다.
•
하지만 생각보다 단순해 보이는 문제지만, 로직을 실제로 구성 할 때는 너무 복잡했다. 생각과 코드가 따로 노는 느낌이 많았다.
•
문제가 혼동을 주었던 부분은 계속해서 문제를 읽다보니 다리의 길이 = 경과 시간 인것을 알게 되었다.
•
생각보다 프로세스는 읽히지만 코드가 길어서 정신이 없다. 이런것을 잘 정리하는것에 익숙해지고싶다.
•
우선 문제를 보고 내가 생각했던 흐름은 다음과 같다.
규칙 찾아내기
우선 FIFO가 필요하다 먼저들어가서 먼저 나간다. -> Queue 자료구조를 사용해야한다.
최대 2대가 들어갈수있는데 truck_weights 2개가 max_weight보다 초과하면 진입안되기때문에 1개만 가야한다.
1개만 통과할땐 2초가 소요된다.(time=길이)
그럼 그 1개만 통과하고, 2번과 3번이 만약 max_weight보다 작으면 두개를 한번에 통과시켜도 된다.
2개가 한번에 통과된다면 1초가 소요된다.(time +1)
이게 파이프처럼 만약 10버티는 다리에 4가 먼저 진입하고 5가 이후에 진입해서 2대가되면, 4가먼저빠지는게 1초, 5가 빠지는게 1초, 그이후에 만약 또 4라면 1초, 마지막에 4가 한번 더 빠져나가는데 1초
우선 Queue 객체는 다리라고 생각하면 되고
다리에 트럭들을 순서대로 넣고 빼는것을 만드는것이 기본
조건으로 Queue에 들어갈 수 있는 조건을 만들어야 한다.
만약 다리에 첫번쨰요소가 들어갔다. 그럼 기본적으로 1초가 상승하고 length만큼 상승할것이다.
그런데 두번째 요소가 들어 갈 수 있다면(둘을 더한값이 최대보다작다면)
마지막요소의 시간만 재면된다. 따라서 +1상태에서 길이만큼 시간이 걸리는게 그 2개가 통과하는 시간이다.
•
이게 생각은 정리가 되는것 같지만 코드로 옮기는것이 생각보다 쉽지는 않았다.
◦
다른 문제풀이를 통해서 힌트를 얻어내며 풀게되었다.
◦
우선 내가 만들어야 하는 배열이 여러개인것부터 정리했어야 했다.
▪
대기큐, 건너는큐, 시간체크용큐, 완료큐
▪
이렇게 각 배열들을 만들고 실제로 요소를 옮겨가는 상황을 시뮬레이션 했어야 했다.
▪
그리고 건너 가는 상황에 대한 로직을 하나씩 작성해나갔으면 풀이에 도전 할 수 있었을것 같다.
문제 풀이
import java.util.LinkedList;
import java.util.Queue;
public class Solution2 {
public int Solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
Queue<Integer> waitQueue = new LinkedList<>(); //대기큐
Queue<Integer> progressQueue = new LinkedList<>(); //건너는중큐
Queue<Integer> timeQueue = new LinkedList<>(); //시간체크용큐
Queue<Integer> completeQueue = new LinkedList<>(); //완료큐
// 우선 모든 차량을 대기큐에 추가
for (int truckWeight : truck_weights) {
waitQueue.add(truckWeight);
}
int minute = 0;
int bridgeWeight = 0;
int bridgeTruckCount = 0;
// 다리를 완전히 지난 트럭 개수와 총 트럭 개수가 같아질 때까지 반복할 것이다.
while (completeQueue.size() != truck_weights.length) {
minute++; // 시간 증가
// 다리를 완전히 지난 트럭의 처리
if (timeQueue.peek() != null && timeQueue.peek() == bridge_length) {
timeQueue.poll(); // 가장 앞에 있는 트럭의 지나간 시간을 큐에서 제거
bridgeWeight -= progressQueue.poll(); // 가장 앞에 있는 트럭의 무게를 다리 무게에서 빼기
bridgeTruckCount -= 1; // 다리 위의 트럭 개수 감소
completeQueue.add(1); // 다리를 완전히 지난 트럭의 개수 증가
}
// 대기 중인 트럭의 처리
if (waitQueue.peek() != null) {
int truck = waitQueue.peek(); // 대기 중인 트럭의 무게
if (truck + bridgeWeight <= weight && bridgeTruckCount < bridge_length) {
bridgeWeight += truck; // 다리 무게에 트럭 무게 추가
bridgeTruckCount++; // 다리 위의 트럭 개수 증가
progressQueue.add(waitQueue.poll()); // [[[대기 중인 트럭을 다리로 이동]]]
timeQueue.add(0); // 다리 위에 올라간 트럭의 지나간 시간 초기화 (0분부터 시작)
}
}
// 다리 위에 있는 각 트럭의 지나간 시간 업데이트
for (int i = 0; i < timeQueue.size(); i++) {
timeQueue.add(timeQueue.poll() + 1); // 다리 위에 있는 트럭의 지나간 시간을 1분씩 증가
}
}
answer = minute; // 최종 소요된 시간 저장
return answer;
}
public static void main(String[] args){
int bridge_length = 2;
int weight = 10;
int[] truck_weights = {7,4,5,6};
Solution2 sol = new Solution2();
System.out.println(sol.Solution(bridge_length,weight,truck_weights));
}
}
Java
복사