[Programmers][python] 7. 문제풀이 실습 (2): 프로그래머스 운송 트럭

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

프로그래머스 - 운송 트럭

문제 설명

XX 회사는 트럭을 이용해 상품을 운반합니다. 트럭은 최대 무게가 한정되어있습니다. 직원은 트럭에 상품을 순서대로 실으며, 상품을 실을 수 없는 트럭은 바로 목적지로 출발합니다. 이때 우리는 모든 상품을 운반하는데 필요한 트럭은 최소 몇 대인지 구하려 합니다.

예를 들어, 각 상품의 스펙이 다음과 같고, 트럭의 허용 무게가 300, 실어야 할 상품이 ["toy", "snack", "snack"]라고 합니다.

이 경우 첫째 상품과 둘째 상품은 같은 트럭에 들어가지만, 셋째 상품은 다른 트럭에 넣어야 합니다. 따라서 필요한 트럭 수는 두 대 입니다.

트럭의 허용 무게 max_weight와 상품의 스펙을 담은 배열 specs, 운반할 상품의 이름이 순서대로 들은 배열 names가 주어집니다. 이때, 상품을 순서대로 운반하기 위해 필요한 트럭 수를 리턴하는 함수, soution을 완성하세요.

제한조건

• max_weight는 1 이상 100,000 이하입니다.
• specs의 길이는 1 이상 100,000 이하입니다.
  • specs의 원소는 [상품 이름, 상품 무게]를 나타냅니다.
  • 상품 이름은 길이가 1 이상 10,000 이하인 문자열입니다.
  • 상품 무게는 1 이상 max_weight 이하인 자연수를 나타내는 문자열입니다.
  • 이름이 같은 상품은 없습니다.
• names는 길이가 1 이상 10,000 이하인 배열입니다.
  • names의 원소는 모두 specs에 있는 상품입니다.

입출력 예

입출력 예 설명

• 입출력 예 #1
  앞서 설명한 예와 같습니다.

• 입출력 예 #2
  모든 상품은 각각 다른 트럭에 들어갑니다.
  두 번째 트럭을 호출하면 첫 번째 트럭은 목적지로 출발하므로, 세 번째 상품을 첫 번째 트럭에 넣을 수는 없습니다.

생각

1. specs의 최대 길이는 10만, names의 최대 길이는 1만으로 수가 큰 것으로 보아 비효율적인 코드를 짜면 안될 것 같다는 생각이 들었습니다.

2. name List는 어쩔 수 없이 순차적으로 확인해야 할 것 같지만 순차적으로 확인할 때마다 specs List에 있는지 없는지 검색을 해야하므로 검색이 느리다면 시간이 매우 많이 걸릴 것입니다.

3. 그래서 specs List를 검색이 $O(1)$의 시간으로 빠른 해시(딕셔너리) 자료구조를 활용하기로 생각했습니다.

4. 먼저 sepcs를 순차적으로 dic_spec에 삽입합니다.
   이 경우, 삽입할 때 드는 시간은 $O(1)$이므로 specs List의 길이에 비례할 것입니다.

5. 그 후, name List를 순차적으로 탐색하며 누적 무게가 max_weight가 넘는지 확인하며,
   넘으면 트럭의 숫자를 +1 합니다.

Code (Python)

def solution(max_weight, specs, names):
    answer = 1
    
    dic_spec = {}
    for spec in specs:
        dic_spec[spec[0]] = int(spec[1])

    st_weight = 0
    for name in names:
        if max_weight < st_weight + dic_spec[str(name)]:
            answer += 1
            st_weight = dic_spec[str(name)]
        else:
            st_weight += dic_spec[str(name)]
    
    return answer

참고

• python 자료형 시간복잡도 정리: https://wayhome25.github.io/python/2017/06/14/time-complexity/

이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.