티스토리 뷰
728x90
[Python]프로그래머스 문제풀이 - 다리를 지나는 트럭
서문
오늘은 프로그래머스 사이트 / 코딩테스트 / 스택,큐 부분 세 번째 문제풀이를 하겠습니다. 문제를 살펴보겠습니다. 😉
- 프로그래머스 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42583
코드의 전개 논리가 궁금하시다면, 밑의 사이트에 들어가서 코드를 작성하여 visualize해주시면 코드가 어떤 식으로 흘러가는지 눈으로 파악하실 수 있습니다!
- 파이썬 튜터 사이트 : http://pythontutor.com/visualize.html#mode=display
1. 문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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 함수를 완성하세요.
2. 제한사항
- bridge_length는 1 이상 10,000 이하입니다.
- weight는 1 이상 10,000 이하입니다.
- truck_weights의 길이는 1 이상 10,000 이하입니다.
- 모든 트럭의 무게는 1 이상 weight 이하입니다.
3. 입출력 예 설명
| bridge_length | weight | truck_weights | return |
|---|---|---|---|
| 2 | 10 | [7,4,5,6] | 8 |
| 100 | 100 | [10] | 101 |
| 100 | 100 | [10,10,10,10,10,10,10,10,10,10] | 110 |
본문
요약
- 다리의 길이와 다리가 견딜 수 있는 중량, 트럭의 무게가 주어진다. 한 스탭에(1초)에 truck을 다리에 올리거나 내리게 할 수 있다.
- 한 스탭( 1초 )에 다리에 트럭을 하나 씩 올릴텐데, 다리에 있는 트럭의 무게가 다리의 중량을 넘으면 안된다.
- 넘을 경우, 다리에 있던 트럭을 먼저 빼야 한다.
- 이때 몇 초가 걸릴 지 return한다.
문제풀이
코드
def solution(bridge_length, weight, truck_weights):
answer = 0
bridge_list = [0] * bridge_length
suc_list = []
while bridge_list:
if bridge_list[0] == 0:
bridge_list.pop(0)
answer += 1
else:
suc_list.append(bridge_list.pop(0))
answer += 1
if truck_weights:
if sum(bridge_list) + truck_weights[0] <= weight:
bridge_list.append(truck_weights.pop(0))
else:
bridge_list.append(0)
return answer결과
문제 실패 (시간 초과)
정확성: 92.9
합계: 92.9 / 100.0
Detail Code Review
- 우선 bridge_list에 요소가 없을 때까지 while문을 돈다. bridge_list에는 다리의 길이만큼 0을 담는다.
- 나는 suc_list에 다리를 지나온 트럭을 담았는데 자세히 생각해보니까 불필요한 작업이었던 것 같다. 이걸 고치면 아마 더 정확한 코드가 되지 않을까...
- 다리의 0번 째 요소가 0이면 꺼내지만 suc_list에 담지 않는다. 아니라면 suc_list에 담는다.
- truck_weight에 트럭이 있으면, 그 트럭을 넣어주어야 한다. 이 때 다리가 견딜 중량을 초과하지 않게 다리의 모든 무게의 합과 이제 넣어줄 트럭의 무게를 합쳐 한계중량과 비교한다. 비교하여 한계중량보다 작다면 다리에 트럭을 올려준다.
- 만약 한계중량을 넘는다면 0을 넣는다.
코드 문제 해결
- sum()함수의 문제 : sum()함수를 꼭 반복문이 진행될 때마다 bridge_list의 합을 계산해주는데 이보다 다리에 올라가는 트럭의 무게만 잘 계산하면 그럴 필요가 없다. sum함수 : O(n)
def solution(bridge_length, weight, truck_weights):
answer = 0
bridge_list = [0] * bridge_length
suc_list = []
bridge_weight = 0
while bridge_list:
if bridge_list[0] == 0:
bridge_list.pop(0)
answer += 1
else:
bridge_weight -= bridge_list[0]
suc_list.append(bridge_list.pop(0))
answer += 1
if truck_weights:
if bridge_weight + truck_weights[0] <= weight:
bridge_weight += truck_weights[0]
bridge_list.append(truck_weights.pop(0))
else:
bridge_list.append(0)
return answer
- sum()을 빼고 truck이 다리에 올라가거나 내려갈때만 bridge_weight라는 변수로 계산해주니 통과되지 않았던 case5가 해결되었다.
혹시 문제가 있는 부분이 있으시면 말씀해주세요.🙄
댓글
