문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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_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 |
🎈 나의 풀이
from collections import deque
def solution(bridge_length, weight, truck_weights) :
answer=0 # 시간
que=deque(truck_weights);
bridge=deque([0]*bridge_length) # 다리
_sum=0
while bridge :
answer+=1
_sum-=bridge.popleft() # 다리에서 트럭이 움직임
if que :
if que[0]+_sum <= weight : # 무게 검사
_sum+=que[0]
bridge.append(que.popleft()) # 다리에 트럭 올리기
else : # 무게가 만족하지 못하면
bridge.append(0)
return answer
앞에 있는 값부터 뽑아야해서 deque 사용
sum()을 사용하니 제출했을 때 5번 테스트케이스가 시간초과 뜬다.
_sum변수로 트럭을 올리거나 뺄 때 갱신해줌.
무게가 만족되지 않아서 트럭을 못올렸을 때, 0을 추가해줬다. 트럭이 앞으로 이동할 수 있도록.
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0; // 시간
int sum=0; // 다리 위 트럭 무게
int idx=0; // truck_weights배열의 인덱스
Deque bridge=new LinkedList(); // 다리
for (int i=0; i<bridge_length; i++){
bridge.offerLast(0);
}
while(!bridge.isEmpty()){ // 다리가 빌 때까지
answer++;
sum-=(int)bridge.pollFirst();
if(idx < truck_weights.length){
if(sum+truck_weights[idx] <= weight){ // 다리 위 무게 확인
bridge.offerLast(truck_weights[idx]); // 다리에 트럭 올리기
sum+=truck_weights[idx];
idx++;
}else{
bridge.offerLast(0);
}
}
}
return answer;
}
}
자바로도 작성해봄!
위 파이썬 코드랑 로직은 같음.
# 제출하니 많이 실패 뜸ㅠ
def solution(bridge_length, weight, truck_weights):
time = 0
distance=0
bridge=[0]*bridge_length # 다리 만들기
while truck_weights: # 트럭이 있을 동안
for i in range(bridge_length):
time+=1
if truck_weights:
time+=1
truck=truck_weights.pop(0)
if sum(bridge)+truck < weight :
if bridge[-1]==0:
bridge[-1]=truck # 트럭이 다리 위에 올라감
else:
bridge.pop(0)
bridge[-1]=truck
bridge.append(0)
else:
bridge.pop(0)
bridge.append(0)
return time
다른사람 풀이는 다리의 무게에 집중. 나는 bridge_length동안에 반복문을 돌리고 1씩 증가시키는게 문제인듯. truck_weights가 []인데 for i in range(bridge_length)가 돌아가면 다리 bridge에 트럭이 없어도 time이 증가하는 경우가 있다.
두번째 문제점은 다리 위에서 트럭이 제대로 움직이지 않은 것.
bridge에 있는 트럭이 앞으로 이동하게. -> bridge에서 앞에 값을 pop하고 뒤에 0을 덧붙임.
-> 먼저 pop하고 현재 다리 위에 있는 트럭들의 무게+들어올 트럭 <= weights이면 트럭을 다리 위에 추가. 그렇지 않다면 0을 추가.
while bridge: # 트럭이 있을 동안
time+=1
if truck_weights != []:
truck=truck_weights.pop(0)
else:
break
이렇게 하면 truck_weights가 없고 bridge에 트럭이 남아있는 경우임에도 불구하고 반복문이 끝나는 문제점이 있다.
# 다른사람 풀이 참고
def solution(bridge_length, weight, truck_weights):
time = 0
bridge=[0]*bridge_length # 다리 만들기
while bridge: # 트럭이 있을 동안
time+=1
bridge.pop(0)
if truck_weights:
if sum(bridge)+truck_weights[0] <= weight :
bridge.append(truck_weights.pop(0)) # 트럭이 다리 위에 올라감
else:
bridge.append(0)
return time
bridge에서 pop을 처음에 하고 무게 조건을 확인하고 트럭 또는 0을 append한다. truck_weights에서 pop하는 것은 조건에 충족했을 때한다. 그렇지 않고 그 전에 하면 무게가 초과되는 경우 0이 append되고 반복문 처음부터 실행되니까 트럭이 누락됨.
def solution(bridge_length, weight, truck_weights):
time = 0
distance=0
bridge=[0]*bridge_length # 다리 만들기
while truck_weights: # 트럭이 있을 동안
time+=1
bridge.pop(0)
if sum(bridge)+truck_weights[0] <= weight :
bridge.append(truck_weights.pop(0)) # 트럭이 다리 위에 올라감
else:
bridge.append(0)
return time+bridge_length
for문 추가하기 전에 짰던 코드가 완전히 잘못된건 아니었다. bridge.pop(0)의 위치, truck_weights 동안에 반복문을 돌리더라도 bridge_length를 더해서 반환하면 되는 것이다.
bridge_length를 더할까도 생각했었는데 ㅠㅠㅠ bridge.pop(0)때문에!!!!
담부터 문제설명 좀 제발 똑같이 보고 만들자,,
🎀 다른사람 풀이
def solution(bridge_length, weight, truck_weights):
q=[0]*bridge_length
sec=0
while q:
sec+=1
q.pop(0)
if truck_weights:
if sum(q)+truck_weights[0]<=weight:
q.append(truck_weights.pop(0))
else:
q.append(0)
return sec
나는 truck_weights에 값이 있을 동안에 반복문을 돌림. 위의 코드는 다리(q)가 있을 동안에 반복한다.
문제 설명을 잘 보자.. 나는 [7]이 아닌 [0, 7]로 짜니까 문제였다. pop을 앞에서 해주고 난뒤 조건을 검사해서 다리가 []이 될 때까지 반복문을 돌린다.
import collections
DUMMY_TRUCK = 0
class Bridge(object):
def __init__(self, length, weight):
self._max_length = length
self._max_weight = weight
self._queue = collections.deque()
self._current_weight = 0
def push(self, truck):
next_weight = self._current_weight + truck
if next_weight <= self._max_weight and len(self._queue) < self._max_length:
self._queue.append(truck)
self._current_weight = next_weight
return True
else:
return False
def pop(self):
item = self._queue.popleft()
self._current_weight -= item
return item
def __len__(self):
return len(self._queue)
def __repr__(self):
return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue))
def solution(bridge_length, weight, truck_weights):
bridge = Bridge(bridge_length, weight)
trucks = collections.deque(w for w in truck_weights)
for _ in range(bridge_length):
bridge.push(DUMMY_TRUCK)
count = 0
while trucks:
bridge.pop()
if bridge.push(trucks[0]):
trucks.popleft()
else:
bridge.push(DUMMY_TRUCK)
count += 1
while bridge:
bridge.pop()
count += 1
return count
def main():
print(solution(2, 10, [7, 4, 5, 6]), 8)
print(solution(100, 100, [10]), 101)
print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]), 110)
if __name__ == '__main__':
main()
from collections import deque
def solution(bridge_length, weight, truck_weights):
bridge = deque(0 for _ in range(bridge_length)) # bridge_length만큼 deque를 생성
total_weight = 0 # 다리 위의 총 트럭 무게
step = 0
truck_weights.reverse() # 거꾸로 뒤집기
while truck_weights:
total_weight -= bridge.popleft()
if total_weight + truck_weights[-1] > weight:
bridge.append(0)
else:
truck = truck_weights.pop()
bridge.append(truck)
total_weight += truck
step += 1
step += bridge_length
return step
deque는 효율이 좋다.
pop대신 popleft를 써소 효율을 높임(그래서 truck_weights.reverse를 한 것이다).
다리 위의 총 트럭 무게 total_weight와 truck_weights에서 맨 끝 값(다리 위에 올라갈 트럭)의 무게 합이 weight보다 크다면 bridge에 0을 추가한다(트럭이 앞으로 나아가는 효과).
sum()을 사용해도 되는데 효율성 때문에 대신 total_weight를 씀.
그렇지 않다면 bridge에 truck을 append한다(트럭을 다리 위에 올린다).
반복문이 끝난 후 시간 step에 bridge_length를 더한 값을 return한다(bridge_length를 채워야 트럭이 빠져나가니까).
문제 출처 👉 프로그래머스
'coding test' 카테고리의 다른 글
| [파이썬] 풍선 터트리기 (0) | 2021.01.04 |
|---|---|
| [파이썬] 조이스틱 (0) | 2020.12.31 |
| [파이썬] 약수의 합 (0) | 2020.12.24 |
| [파이썬] 이진 변환 반복하기 (0) | 2020.12.24 |
| [파이썬] 시저 암호 (0) | 2020.12.24 |