프로그래머스 - 다리를 지나는 트럭

이번 글에서는 프로그래머스에 게시된 다리를 지나는 트럭 문제를 풀어 보겠다.

programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭

 

이 문제는 정해진 무게의 트럭들이 순서대로 다리를 통과하는데 걸리는 시간을 구하는 문제이다. 다만 다리가 버틸 수 있는 무게가 정해져 있으며 꼭 정해진 순서대로 다리를 지나가야한다. 이 문제는 간단해 보였지만 실제로 문제를 풀다보니 생각보다 이것저것 신경써야될게 많아서 거의 세시간 정도를 잡아 먹었다. 딱봐도 Queue를 써야 될 것 같은 문제였지만 저자는 ArrayList가 더 효율적이라고 생각되어 ArrayList 만으로 문제를 풀었다. 

 

풀이

 

 

간단히 변수들에 대해서 설명을 하자면, 

weightOnBridge = 현재 다리에 있는 트럭들의 무게

trucksOnBridge = 현재 다리에 있는 트럭들이며 각 element는 현재 다리의 어느 구간에 있는 지를 나타낸다

 

24줄에서 while loop을 시작 할때 다리를 통과한 트럭의 수(exitCnt) 가 통과 해야될 트럭의 수(truck_weights.length) 보다 작으면 계속 순환한다. 26번줄은 다리위의 모든 트럭을 1만큼 이동시키는 구문이다. 27번줄은 만약 다리위의 가장 선두 트럭이 다리를 넘어가면 28번줄에서 무게를 빼어준다. 주목 할 부분은 exitCnt, enterCnt 둘다 수만을 세는 것이 아닌 인덱스의 용도로도 쓰여지고 있다는 것이다. 34번줄에서는 만약 대기중인 트럭이 아직 있고 대기중인 트럭이 들어와도 다리가 견딜수 있는 무게이면 트럭을 다리위에 진입시킨다.

 

걱정 되는 부분이 있다면 26번줄에 replaceAll 메소드가 시간복잡도가 높지 않을까 예상된다.