문제
프로그래머스 코딩테스트 고득점 Kit -
스택/큐
- Lv 2. 다리를 지나는 트럭 (Python)
https://school.programmers.co.kr/learn/courses/30/lessons/42583
코드 구현
def solution(bridge_length, weight, truck_weights):
answer = 0
# 다리에는 트럭이 최대 bridge_length대 올라갈 수 있음
# 다리는 weight 이하까지의 무게를 견딜 수 있음
bridge = [0 for _ in range(bridge_length)] # 다리 큐 (다리 길이만큼의 배열을 선언하여 한칸씩 밀리며 트럭이 지나갈 예정)
### 정답 코드
sum_weight = 0 # 다리 위 트럭의 무게 합
while(len(bridge) > 0):
sum_weight -= bridge.pop(0) # 다리 큐가 밀리면서 차가 지나가게 된다면 다리의 무게 합에서 빼주어야 함
answer += 1
if(len(truck_weights) > 0): # 대기 트럭이 남아있지 않을 때까지 반복
if(truck_weights[0] + sum_weight <= weight): # 현재 다리 위의 트럭 무게 + 대기 트럭 무게가 다리를 건널 수 있는 무게라면
sum_weight += truck_weights[0] # 다리 위에 해당 트럭이 올라가면 무게 합에 더해줌
bridge.append(truck_weights.pop(0)) # 다리 위에 올라감
else:
bridge.append(0) # 지나갈 수 없는 무게라면 못 올라가지만 트럭들은 이동해야 하므로 0을 추가하며 밀어줌
return answer풀이
- 정말 오래 걸려서 풀었다… 처음에는 문제가 너무 애매하게 쓰여있어서 많이 해맨 것 같다 ㅠㅠ
- 트럭은 1초에 1칸 움직이고 다리의 길이만큼 움직여야 다리를 다 지나간 것이 된다는 내용같은게 빠져있어서 예제 중에 첫번째 예제만 맞췄는데 나머지 두개의 예제를 틀리게 되고 그랬다 … 흑
- 질문하기에 나와있는 문제에 대한 자세한 설명 참고 : https://school.programmers.co.kr/questions/53163
따라서 첫번째로 짰던 코드는 아래와 같다. 예제는 통과하였지만 테스트케이스들을 주르륵 틀렸었다.
### 이전 코드 (테케 실패)
def solution(bridge_length, weight, truck_weights):
answer = 0
can_pass = []
for truck in truck_weights:
if ((sum(can_pass) + truck) > weight or len(can_pass) + 1 > bridge_length):
while(len(can_pass) > 0):
can_pass.pop(0)
answer += bridge_length
can_pass.append(truck)
if(len(can_pass) > 0):
trucks = 0
while (len(can_pass) > 0):
can_pass.pop(0)
trucks += 1
answer += bridge_length + trucks
return answer- 처음에는 이 코드에서 도저히 어디를 고쳐야할지 막막하여 질문하기를 뒤져 힌트들을 살짝 참고하였다.
- 다리의 길이를 정해주어 큐로 설정하고, 이를 계속 반복하여
pop해주고append해주는 식으로 해야한다는 힌트를 얻었다.
배열을 통해 큐를 만들어주어 다리를 만들고 이 위에 트럭을 올리고 빼주는걸 반복하는 두번째 코드
## 테스트케이스 5번 시간초과
def solution(bridge_length, weight, truck_weights):
answer = 0
bridge = [0 for _ in range(bridge_length)] # 다리 큐 (다리 길이만큼의 배열을 선언하여 한칸씩 밀리며 트럭이 지나갈 예정)
while(len(bridge) > 0):
bridge.pop(0) # 다리 큐 한칸씩 밀기
answer += 1 # 밀게 되면 차가 지나가게 되므로 시간 + 1
if(len(truck_weights) > 0): # 대기 트럭이 남아있지 않을 때까지 반복
if(truck_weights[0] + sum(bridge) <= weight): # 현재 다리 위의 트럭 무게 + 대기 트럭 무게가 다리를 건널 수 있는 무게라면
bridge.append(truck_weights.pop(0)) # 다리에 올라감
else:
bridge.append(0) # 지나갈 수 없는 무게라면 못 올라가지만 트럭은 지나가야 하므로 0을 추가하여 밀어주는 형태 완성
return answer- 그러나
sum(bridge)로 인해 5번 테스트케이스에서 시간초과가 발생하게 된다. - 따라서
sum을 사용하지 않고,sum_weight변수를 생성하여 이를 가감하는 방식으로 변경한게 제일 위에 있는 정답 코드가 되었다.
What I learned
찾아보니 정답 코드들은 대부분 deque를 사용하여 해결한 것 같다…!
▶️ from collections import deque
deque: 큐의 앞, 뒤에 자료 넣고 빼기가 가능한 자료구조- 리스트와 비슷한 메서드들을 다 가지고 있음 (append, pop, remove, reverse, index, insert, count, clear …)
- 참고 자료 : https://velog.io/@nayoon-kim/파이썬-deque, https://wikidocs.net/104977
주로 사용되는 메서드들 + 기억할 메서드들
▶️ deque.append(x) : 큐의 맨 뒤에 요소 삽입
>>> from collections import deque
>>> d = deque([1, 2, 3, 4, 5])
>>> d.append(6)
>>> d
deque([1, 2, 3, 4, 5, 6])▶️ deque.appendleft(x) : 큐의 맨 앞에 요소 삽입
>>> from collections import deque
>>> d = deque([1, 2, 3, 4, 5])
>>> d.appendleft(0)
>>> d
deque([0, 1, 2, 3, 4, 5])▶️ deque.pop() : 큐의 맨 뒤를 제거, 반환
>>> from collections import deque
>>> d = deque([1, 2, 3, 4, 5])
>>> d.pop()
5
>>> d
deque([0, 1, 2, 3, 4])▶️ deque.popleft() : 큐의 맨 앞을 제거, 반환
>>> from collections import deque
>>> d = deque([1, 2, 3, 4, 5])
>>> d.popleft()
0
>>> d
deque([1, 2, 3, 4, 5])▶️ deque(큐에 넣을 요소, maxlen) : 큐 생성 시 maxlen 지정 가능
- 요소를 추가하였을 때,
maxlen을 넘어간다면 → 제일 왼쪽 요소부터 밀려 없어지며 추가되어maxlen을 유지한다.
>>> from collections import deque
>>> queue = deque('fnd', 3)
>>> queue
deque(['f', 'n', 'd'], maxlen=3)
>>> queue.append('b')
>>> queue
deque(['n', 'd', 'b'], maxlen=3)
>>> queue.append('c')
>>> queue
deque(['d', 'b', 'c'], maxlen=3)
>>> queue.appendleft('a')
>>> queue
deque(['a', 'd', 'b'], maxlen=3)
>>> print(queue.maxlen)
3
데굴데굴 뚝딱뚝딱 개발기록