문제
강의에 들어있는 문제라서 문제 링크를 걸어도 되는지 모르겠다.
한정된 트럭 용량에 순서대로 상품들을 실을 때, 몇 대의 트럭이 필요한지 구하는 문제이다.
트럭의 허용 무게 : max_weight
상품별 무게 : specs
운반할 상품이 순서대로 담긴 배열 : names
1 <= max_weight <= 100,000
1 <= specs의 길이 <= 100,000
1 <= names의 길이 <= 10,000
입출력 예시
| max_weight | specs | names | return |
|---|---|---|---|
| 300 | [[“toy”,”70”], [“snack”, “200”]] | [“toy”, “snack”, “snack”] | 2 |
| 200 | [[“toy”,”70”], [“snack”, “200”]] | [“toy”, “snack”, “toy”] | 3 |
접근
specs 배열을 어떻게 관리할 지가 관건 인 것 같다.
매번 specs 배열에서 필요한 상품의 무게를 찾으려한다면 효율성을 통과할 수 있을까?
아마 못할 것 같다.
파이썬은 딕셔너리가 존재하니, 편하게 딕셔너리를 이용해주자.
specs을 리스트에서 딕셔너리로 바꿔주고 나면 names 길이만큼만 루프를 돌면서 쉽게 답을 구할 수 있다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
def solution(max_weight, specs, names):
dic = dict(specs)
now_w = max_weight
answer = 1
for name in names:
val = int(dic[name])
if val <= now_w:
now_w -= val
else:
answer += 1
now_w = max_weight - val
return answer