[프로그래머스 알고리즘] 프로그래머스 Lv.2: 다리를 지나는 트럭 / 파이썬 Python3 (스택/큐)
🔔 문제
출처 : https://programmers.co.kr/learn/courses/30/lessons/42583
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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_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 |
※ 공지 - 2020년 4월 06일 테스트케이스가 추가되었습니다.
📝 풀기 전…
사실, 이 문제는 플레이데이터에서 제시되었던 문제이면서 동시에, 옛날부터 꼭 풀고 싶었던 문제였다.
내 눈에는 재밌어 보이는 문제였어서 풀면 기분이 되게 좋을 것 같았다.다른 측면에서는, 작년의 나와 지금 이 문제를 풀려고 시도하고 있는 내가 다르다는 것도 느껴져서 좋았다.
그러나… 아직 나는 많이 부족하고😥
아직 배가 고프다.
🔐 해결 (소스 코드)
def solution(bridge_length, weight, truck_weights):
answer = 0
# 다리 길이 만큼 0 채워서 다리 리스트 정의
bridge = [0 for _ in range(bridge_length)]
# bridge 리스트의 길이가 0이 아닐때만 while문 반복
while bridge:
answer += 1 # 시간 더하기
bridge.pop(0)
if len(truck_weights) > 0: # 트럭 대기 리스트의 길이가 0이 아닐 때까지 반복하도록 조건 설정
# 다리 위에 있는 트럭들의 무게 합과 대기중인 다음 차례의 트럭 무게가 조건을 만족할 시
if (sum(bridge) + truck_weights[0]) <= weight:
truck = truck_weights.pop(0)
bridge.append(truck) # 다리 리스트에 추가
else: # 만족 못할 시
bridge.append(0) # 0을 추가해서 다리의 길이 유지
return answer
💪 후기
이 문제를 끝으로 프로그래머스 코딩테스트 고득점 Kit에 제시되어있는 ‘스택/큐’ 문제는 다 풀었다.
그러나, 틈틈이 생각나고 필요할 때마다 이 문제들을 보면서 참고하고, 공부해야 된다고 생각하고 있다.
(기본적인 자료구조니까)(그리고, 백준 문제만 해도 아직 많이 남아있다 ㅋㅋ)아까 위에서 말했듯이 작년의 나와 지금의 나는 다른 수준이긴 하나… 여전히 부족한 실력이다.
좋은 개발자가 되고, 좋은 회사로 들어가려면 이보다 수준 높게 준비된 상태가 되어야만 하기 때문이다.참 쉽지는 않지만, 재미를 느끼면서 하고 있기 때문에 너무 좋다.
수준 높은 실력을 갖춘 미래의 나를 보기 위해… 화이팅! 💪
Leave a comment