▶문제설명
코딩테스트 연습 > 스택/큐 > 다리를 지나는 트럭
▶ 설계
트럭을 구조체로 관리하자.
그리고 다리 위에 있는 트럭들을 queue 자료구조로 관리하자.
여러 대의 트럭이 한 시간에 동시에 다리 위로 올라가는 경우는 없으니 도착할 시간이 중복되는 경우는 없다.
시간을 1초씩 증가시키면서 모든 트럭들이 다리를 지날 때까지 반복하면 될 것으로 보인다.
commingTrucksQ의 front에 있는 트럭이 도착할 시간이 되었을 때 하나씩 pop해주자.
그러기 위해서 구조체에 도착 시간을 나타내는 arrivedTime이 필요하다.
또한, 다리 위에 올라와있는 트럭이 빠져나갈 때 그 트럭의 무게를 알아야 현재 다리 위에 얼만큼의 무게가 실리고 있는지 파악할 수 있다. 그래서 구조체에 weight가 필요하다.
▶ 구현
truck_weight.size()가 전체 트럭의 수를 리턴하도록 주어졌다.
while문으로 다리를 건넌 트럭의 수와 전체 트럭의 수가 같아질 때까지 반복했다.
다리 위에서 시작하는게 아니라 다리 위로 올라가는 데에도 1초가 걸리므로 반복문 내에서 가장 먼저 time을 증가시켜줬다.
현재 시간에 다리 위에서 가장 앞에 있는 트럭이 다리를 건넘과 동시에 아직 출발하지 않은 트럭이 다리 위로 올라올 수 있다.
그러므로 가장 앞의 트럭이 다리 위에서 빠져나갈 수 있는지를 먼저 확인해서 빼준 뒤, 다리 위에 트럭을 올려주어야한다.
가장 앞에 있는 트럭인 commingTrucksQ.front()의 arrivedTime이 현재 시간과 같다면 가장 앞의 트럭이 다리를 건넜다는 뜻이 된다. 이 때 다리 위에 올라와있는 트럭의 무게의 합에 다리를 건넌 트럭의 무게만큼을 빼주어야한다.
다리 위에 올라와있는 트럭의 무게의 합이 다리가 견딜 수 있는 무게와 같거나 작은 경우에만 트럭을 commingTrucksQ에 push한다. 이 때 다리 위에 올라와있는 트럭의 무게의 합에 다리를 건넌 트럭의 무게만큼을 더해주어야한다.
현재 트럭이 다리에 올라간 시간 + bridge_length가 현재 트럭이 다리를 건넜을 때의 시간이 된다.
현재 트럭을 나타내는 인덱스는 begin이라는 변수로 관리했다.
트럭이 다리를 건널 때마다 카운트해서, 모든 트럭이 건넜을 때 반복을 종료했다.
그리고 반복이 종료되었을 때의 시간이 모든 트럭이 다리를 지나는 데 걸리는 최소 시간이 된다.
※ 테스트 해보니 STL의 queue 자료구조에서는 queue가 비어있을 때 front값을 참조할 경우 0을 반환하도록 되어있었다.
▶Solution
'■ 알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 단어 변환 (0) | 2019.12.16 |
|---|---|
| [프로그래머스] 소수 찾기 (0) | 2019.12.14 |
| [프로그래머스] 여행경로 (0) | 2019.12.12 |
| [프로그래머스] 기능개발 (0) | 2019.12.12 |
| [프로그래머스] 땅따먹기 (0) | 2019.01.03 |