kotlin 프로그래머스 lv2 다리를 지나는 트럭
문제를보고 저번에 풀었던 "숫자 변환하기" 문제와 유사하여 queue를 이용해서 해결했다.
예시를 보면 트럭2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있다고 한다.
무게가 [7,4,5,6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 한다고 한다.
- 숫자 변환하기
그래서 나는 먼저 다리 위에 있는 트럭 배열을 LinkedList를 이용해서
onBridge변수를 초기화 했다.
그 후 다음으로 다리에 진입할 트럭의 인덱스 변수를 초기화했다.
마지막으로 모든 트럭이 다리를 건널 때까지 반복하는 작업을 했다.
여기서 while문의 조건은 onBridge 배열이 비어있지 않거나
다음 트럭의 인덱스가 주어직 매개변수 nextTruckIdx의 사이즈보다 작으면
answer을 증가시킨다.
while문안에서는 2 가지 조건을 확인하는데
1. 다리를 완전히 건넌 트럭이 있는지 확인
2. 다리에 다음 트럭이 들어갈 공간이 있는지 확인
이 두가지를 확인해줘야 한다.
이 2 코드를 살펴보면 먼저 peek(), poll() 메서드를 사용했는데
두 메서드는 아래의 표에 정리하였다.
| ※ peek(), poll() 메서드 peek() : LinkedList의 첫 번째 요소를 반환한다. 이 메서드는 LinkedList가 비어 있지 않은 경우에만 사용할 수 있다. 그렇지 않으면 예외가 발생한다. LinkedList에서 요소를 제거하지 않고 첫 번째 요소를 반환한다. 따라서 리스트가 비어 있지 않고 요소가 있다면, 첫 번째 요소를 반환하지만 리스트에서 제거되지는 않는다. poll(): LinkedList의 첫 번째 요소를 제거하고 반환한다. 이 메서드는 LinkedList가 비어 있지 않은 경우에만 사용할 수 있다. 그렇지 않으면 null을 반환한다. LinkedList에서 첫 번째 요소를 제거하고 반환한다. 따라서 리스트가 비어있지 않고 요소가 있다면, 첫 번째 요소를 반환하고 리스트에서 제거된다. poll 메서드는 리스트에서 요소를 제거하면서 반환해야 할 때 유용하다. |
1. 다리를 완전히 건넌 트럭이 있는지 확인하는 코드는
다음과 같다.
-다리에 트럭이 있는지 여부를 확인하고, onBridge가 비어있지 않으면 다리에 트럭이 있음을 의미
-answer-onBridge.peek().second>= bridge_length: 다리에 있는 첫 번째 트럭이 다리를 완전히 건너는데 필요한 시간(다리에 진입한 시간을 뺀 값)이 bridge_length 이상인지 확인.
다리를 완전히 건넌 트럭의 경우, answer에서 트럭이 다리에 진입한 시간을 뺀 값이 다리를 건너는데 필요한 시간과 같거나 크게된다.
-totalWeight -= onBridge.poll().first : 다리를 완전히 건넌 트럭의 무게를 totalWeight에서 빼고, 해당 트럭을 onBridge에서 제거한다. poll()함수는 onBridge에서 첫 번째 요소를 제거하고 반환하며, 여기서는 트럭의 무게를 반환한다. 이를 통해 다리에서 건넌 트럭의 무게를 총 무게에서 빼주게 된다.
2. 다리에 다음 트럭이 들어갈 공간이 있는지 확인
nextTruckIdx < truck_weights.size: 다음 트럭이 트럭 배열의 범위 내에 있는지 확인
nextTruckIdx가 트럭 배열의 크기보다 작으면 다음 트럭이 존재함을 의미
nextTruckIdx < truck_weights.size: 다음 트럭이 트럭 배열의 범위 내에 있는지 확인
nextTruckIdx가 트럭 배열의 크기보다 작으면 다음 트럭이 존재하는 것을 의미
totalWeight + truck_weights[nextTruckIdx] <= weight: 다음 트럭이 다리에 진입해도 다리가 견딜 수 있는 최대 무게를 초과하지 않는지 확인
현재 다리 위에 있는 트럭의 총 무게(totalWeight)에 다음 트럭의 무게를 추가한 값이 다리가 견딜 수 있는 최대 무게(weight)보다 작거나 같으면 다음 트럭이 다리에 진입할 수 있음
onBridge.offer(Pair(truck_weights[nextTruckIdx], answer)): 다음 트럭이 다리에 진입할 수 있는 경우,
onBridge 리스트에 해당 트럭과 진입한 시간의 쌍을 추가
이때 진입한 시간은 현재 시간(answer)으로 설정
totalWeight += truck_weights[nextTruckIdx]: 다음 트럭이 다리에 진입한 후,
현재 다리 위에 있는 트럭들의 총 무게를 업데이트
새로 진입한 트럭의 무게를 추가
nextTruckIdx++: 다음 트럭이 다리에 진입한 후, 다음으로 진입할 트럭의 인덱스를 증가
문제를 풀때 전에 풀었던 유형과 비교하여 풀어서 오랜 시간이 걸리진 않았지만
앞으로도 같은 유형을 반복해서 풀어야겠다.