[Programmers] 다리를 지나는 트럭 (Python3)
from collections import deque def solution(bridge_length, weight, truck_weights): bridge = deque([0]*bridge_length) time = 0 b_weight = 0 while truck_weights: if b_weight==0: bridge[-1]=truck_weights[0] b_weight = truck_weights[0] del truck_weights[0] else: #트럭을 한칸씩 앞으로 움직이기 if bridge[0] != 0: b_weight -= bridge[0] bridge.popleft() bridge.append(0) if b_weight + truck_weights[0] <= weight: #무게가 되면 bridge[-1]=(truck_weights.pop(0)) # 다리에 트럭 올리기 b_weight += bridge[-1] time+=1 time += bridge_length #마지막으로 들어간 트럭 지나가는 시간 return time | cs |
생각보다 오래 걸렸던 문제.
고려해야 할 것은,
1. 처음에 다리위의 트럭 무게들을 구하는데 sum()을 사용했다. 하지만 트럭이 들어갈때와 나올때만 고려해주면 sum()을 사용하지 않을 수 있다. sum()의 시간복잡도는 O(N) 이므로 성능이 느려질수밖에 없다.
2. 그 외에도 트럭을 한 칸씩 움직이는데 bridge_length만큼 반복하면서 bridge[i]를 일일이 검사했다. pop, append만 해주면 되는데 ..
이번에 알게 된 것은 for문은 굉장히 신중하게 사용할 것!
그리고 비슷한 용도로 사용되는 메서드들의 시간복잡도가 모두 다르므로 모두 고려해야 한다는 점.
[시간복잡도 정리]
list
| Operation | Example | Big-O | Notes |
|---|---|---|---|
| Index | l[i] | O(1) | |
| Store | l[i] = 0 | O(1) | |
| Length | len(l) | O(1) | |
| Append | l.append(5) | O(1) | |
| Pop | l.pop() | O(1) | l.pop(-1) 과 동일 |
| Clear | l.clear() | O(1) | l = [] 과 유사 |
| Slice | l[a:b] | O(b-a) | l[:] : O(len(l)-0) = O(N) |
| Extend | l.extend(…) | O(len(…)) | 확장 길이에 따라 |
| Construction | list(…) | O(len(…)) | 요소 길이에 따라 |
| check ==, != | l1 == l2 | O(N) | 비교 |
| Insert | ㅣ.insert(i, v) | O(N) | i 위치에 v를 추가 |
| Delete | del l[i] | O(N) | |
| Remove | l.remove(…) | O(N) | |
| Containment | x in/not in l | O(N) | 검색 |
| Copy | l.copy() | O(N) | l[:] 과 동일 - O(N) |
| Pop | l.pop(i) | O(N) | l.pop(0):O(N) |
| Extreme value | min(l)/max(l) | O(N) | 검색 |
| Reverse | l.reverse() | O(N) | 그대로 반대로 |
| Iteration | for v in l: | O(N) | |
| Sort | l.sort() | O(N Log N) | |
| Multiply | k*l | O(k N) | [1,2,3] * 3 » O(N**2) |
Dict
| Operation | Example | Big-O | Notes |
|---|---|---|---|
| Index | d[k] | O(1) | |
| Store | d[k] = v | O(1) | |
| Length | len(d) | O(1) | |
| Delete | del d[k] | O(1) | |
| get/setdefault | d.method | O(1) | |
| Pop | d.pop(k) | O(1) | |
| Pop item | d.popitem() | O(1) | |
| Clear | d.clear() | O(1) | s = {} or = dict() 유사 |
| View | d.keys() | O(1) | d.values() 동일 |
| Construction | dict(…) | O(len(…)) | |
| Iteration | for k in d: | O(N) |
No comments: