오늘 코드카타 너무 복잡해서 울 뻔 했다
다리를 지나는 트럭
문제 설명
첫 번째 예시로 설명해보자면
다리의 길이는 2이고, 다리 위에 올라갈 수 있는 최대 무게는 10이다.
현재 다리를 건너야 하는 트럭은 총 4대이며 각각 무게가 truck_weights에 저장되어 있다.
순서대로 트럭이 올라갈 때, 7이 먼저 올라가고 다음 4가 올라갈 수 있는데(다리의 길이가 2이므로 2대가 올라갈 수 있음) 7+4는 11이므로 무게를 초과한다. 그러므로 7인 트럭이 내려가고 4인 트럭이 올라갈 수 있다.
4트럭 다음인 5트럭이 올라오는데 4+5는 9이므로 2대가 다리 위에 올라갈 수 있다.
이런식으로 다리 위에 모든 트럭을 통과시키고 걸린 시간을 반환하는 문제이다.
시행착오 및 풀이 방법
우선 큐로 풀어야 하는 것은 알았지만 한 번에 풀지 못해서 다른 사람들의 풀이를 참고했다. (자존심 상해)
정답 풀이
- 대기하고 있는 트럭, 현재 다리 위에 있는 트럭, 다리 위에 있는 트럭들이 다리 위에 있었던 시간을 담은 큐 3개를 만든다.
- 전체 시간, 처리한 트럭 갯수, 현재 다리 위에 있는 트럭 갯수, 현재 다리 무게를 저장할 변수를 선언한다.
- 처음 들어온 트럭을 대기 큐에 넣는다.
- 처리한 트럭 갯수와 처음 들어온 트럭 갯수가 동일해질때동안 while문으로 반복
4-1. while문이 돌 때마다(트럭이 올라가거나 내려가거나 = 한 트럭의 변화가 있을 때마다) 시간은 증가하므로 minute++; - 트럭 올리기 - 현재 도로에 있는 트럭들의 무게와 들어오는 트럭의 무게 합이 weight보다 작고, 현재 도로에 있는 트럭의 갯수가 다리의 길이보다 짧으면 트럭을 더 올려도 됨
5-1. 다리에 트럭 추가
5-2. 다리 무게에 들어온 트럭 무게 추가
5-3. 다리에 있는 트럭 갯수 증가
5-4. 해당 트럭의 시간을 시간 큐에 넣기(0)
5-5. 해당 트럭을 다리 위에 올렸으므로 대기 큐에서 삭제 - 올리고 시간이 지났으므로 시간 큐에서 시간 증가 (올리자마자 1초 증가함)
- 트럭 내리기 - 도로가 꽉 찼다면 = 해당 트럭이 도로 위에 있을 시간이 다 되었다면 트럭을 내려야 한다.
7-1. 현재 다리 무게에서 내린 트럭 무게 빼기
7-2. 현재 다리 위의 트럭 갯수 감소
7-3. 해당 트럭의 시간 삭제
7-4. 현재 다리 위의 트럭 삭제
7-5. 트럭 하나가 내려갔으므로 총 처리 트럭 갯수 증가 - 총 트럭 갯수와 처음 들어온 트럭 갯수가 같아지면 모든 트럭을 처리한 것이므로 minute 시간 반환
정답 코드
//queue 사용
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
//대기하고있는 트럭
Queue<Integer> wait_q = new LinkedList<>();
//다리 위에 있는 트럭
Queue<Integer> now_q = new LinkedList<>();
//다리 위에 있는 트럭 시간
Queue<Integer> time_q = new LinkedList<>();
//전체 시간
int minute = 0;
//처리한 트럭 갯수
int total_count = 0;
//현재 다리 위에 있는 트럭 갯수
int bridge_truck_count = 0;
//다리 무게
int bridge_weight = 0;
//처음 들어온 트럭 대기 큐에 넣기
for(int t:truck_weights) {
wait_q.add(t);
}
//처리한 트럭 갯수와 처음 들어온 트럭 갯수가 일치할 때까지 반복
while(total_count != truck_weights.length) {
minute++; //총 시간
//트럭 내리기
//도로가 꽉찼다면 = 해당 트럭이 도로위에 있을 시간이 다 되었다면
if(!time_q.isEmpty() && time_q.peek() == bridge_length) {
bridge_weight -= now_q.peek(); //현재 다리 무게에서 내린 트럭 무게 빼기
bridge_truck_count--; //현재 다리위의 트럭 갯수에서 하나 빼기
time_q.poll(); //해당 트럭의 시간 삭제
now_q.poll(); //현재 다리 위의 트럭 삭제
total_count++;
}
//트럭 올리기
//대기하고 있는 트럭이 있다면
if(!wait_q.isEmpty()) {
int truck = wait_q.peek();
//현재 도로에 있는 트럭들의 무게와 들어오는 트럭의 무게가 weight보다 작고
//트럭의 갯수가 다리 길이보다 작다면 트럭을 더 올려도 됨.
if(bridge_weight+truck <= weight && bridge_truck_count <= bridge_length) {
now_q.add(truck); //다리에 트럭 추가
bridge_weight += truck; //다리 무게에 트럭 무게 추가
bridge_truck_count++; //다리에 있는 트럭 갯수 추가
time_q.add(0); //시간큐에 0 넣기
wait_q.poll(); //다리 위에 올렸으므로 대기 큐에서 삭제
}
}
//다리 위에 머문 시간 증가
for(int i=0; i<time_q.size(); i++) {
time_q.add(time_q.poll()+1);
}
}
return minute;
}
}시행착오
//트럭 내리기
//도로가 꽉찼다면 = 해당 트럭이 도로위에 있을 시간이 다 되었다면
if(!time_q.isEmpty() && bridge_truck_count == bridge_length) {
bridge_weight -= now_q.peek(); //현재 다리 무게에서 내린 트럭 무게 빼기
bridge_truck_count--; //현재 다리위의 트럭 갯수에서 하나 빼기
time_q.poll(); //해당 트럭의 시간 삭제
now_q.poll(); //현재 다리 위의 트럭 삭제
total_count++;
}if(!time_q.isEmpty() && bridge_truck_count == bridge_length)
난 여기서 좀 막혔었다.
다리가 꽉 찼을 경우만 생각해서 현재 다리 위에 있는 트럭의 갯수와 다리의 길이가 같아지면 꽉 찬 것이라 생각해서 트럭을 내려야 한다고 생각했다.
근데 이러면 무한루프에 빠져버린다.!!
곰곰히 생각해보니 7트럭 같은 경우는 bridge_truck_count가 1이지만 (뒤의 4트럭을 못올리니깐) 시간은 2초가 되어서 다리의 끝에 도달했다. 그럼 내려야 하는데 해당 조건에서 내리지 못해서 무한루프에 빠졌던 것 같다. 그러니 시간으로 계산하는 게 맞는 코드!
최근 풀었던 코테중에 가.장 복잡했던 것 같다......
그림으로 다리를 몇개를 그린건지.... 하지만 난 그림을 안그리면 이해가 잘 안돼서 풀지 못한다ㅜㅜㅜ
이거 푸는 데 2시간 걸렸다. 진심 만우절 장난같다
