Programmers 다리를 지나는 트럭 Java

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_lengthweighttruck_weightsreturn

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

출처

 

---

풀이

[첫번째 풀이 방법] - Queue & Array

• 처음 접근 방식
  • 각 트럭의 시간을 배열 형태로 선언하여 각 시간을 증가시켜 주는 부분으로 진행했다.
  • 원래 의도는 해당 트럭이 Queue에 포함되 있으면 해당 트럭에 해당하는 시간 배열을 증가시켜주자는 의미였다.
  • 하지만 이 부분에서 Queue에서 해당 트럭을 접근하는 방식이 contains( Queue의 value값을 비교하여 가지고 있는지 true/false 를 반환 ) 하는 내용밖에 생각이 떠오르지 않자 풀이 방식을 변경하였다.

---

[두번째 풀이 방법] - Queue & Queue

 

[ SOLUTION ]

•  Class 선언
  • 첫번째 풀이 방법에서 "시간" , "무게" 를 중심으로 풀이를 하는 것을 핵심을 가져왔다.
  • 이후 Class 를 선언하여 트럭의 시간값과 무게값을 가져왔다.

• 두 개의 Queue를 선언
  • 첫번째 풀이 방법에서 "next_truck" 을 이용하여 값을 다음 트럭을 가리키려 노력했지만 이번 방법에서 그 트럭이 가지고 있는 무게와 시간값을 가져오기 위해 truckList Queue에 넣어 사용을 하였다.
  • 기존의 Bridge를 기준으로 현재 다리위에 올라가있는 트럭을 확인하기 위해 bridge Queue를 사용했다.
  • 이후 truckList Queue에는 for문을 통해 기존의 truck_weights의 값들을 weight에 저장하였고 time은 0으로 초기화 하여 Queue에 넣었다.

• 핵심 Solution While문

• 첫번째로 while문은 bridge Queue와 truckList 둘 중 하나의 빌때까지 작동한다.
• time 변수를 사용하여 while문이 순환할때마다 전체 트럭들이 이동이 완료될때 까지의 시간을 count올려준다.
• 이후 bridge Queue에 대한 내용이 먼저 나온다.
  
  • 먼저 다리의 가장 앞을 달리는 트럭의 시간값을 지금 현재 카운트 중인 전체 시간값 time에서 뺀다.
  • 이유는 뒤에서 설명을 하도록하겠다.
  • 이후 이 값을 전체 다리의 길이랑 비교하여 조건문을 만들어준다.
  • 조건이 성립되면 이 트럭은 다리의 길이를 벗어나 달리고 있다고 확인을 하여 전체 무게에서 현재 달리는 트럭의 무게를 빼주고 그 트럭을 Queue에서 삭제시켜준다.
• 이후 truckList Queue에 대한 내용이 나온다.
  • 문제 조건에서 다리가 버틸 수 있는 무게가 트럭의 무게를 넘지 않는다면 트럭이 추가가 가능하고 트럭의 무게가 다리가 버틸 수 있는 무게를 넘어서면 추가 트럭이 진입이 어렵다는 내용을 조건문으로 작성한다.
  • 이후 트럭이 추가될 수 있는 조건에 들어서면, 해당 해당 트럭을 선언한 Truck 객체 형태로 trucklist에서 가져온다.
  • 이후 전체 다리가 버티고 있는 무게에 트럭 무게를 합쳐준다.
  • 이후 bridge Queue에 추가되는 트럭의 무게와 count된 지금 현재의 시간을 넣어준다. 이 부분이 앞서 뒤에서 설명한다는 설명 내용이다. count 되고 있는 time의 값을 트럭이 진입할때 넣어주고 나중에 이 트럭이 다리를 벗어날때 최초 들어간 time 값과 현재 count된 time값을 비교하면 다리의 전체 길이인 " bridge_length " 값보다 작은지 큰지를 비교할 수 있는 기준이 된다.

• while문안에서 if문의 순서가 중요하다.
  • while문 전체의 조건이 두개의 Queue중 하나의 Queue가 Empty형태가 된다면 멈추기때문에 우선적으로 bridge의 Queue가 비었는지 확인을 하여 최소 시간 값을 가져오도록 한다.