[python] 프로그래머스 - 다리를 지나는 트럭

 

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42583

 

트럭은 뚠뚠 오늘도 뚠뚠..

1일 1문제인데...이 문제 고민하는데 시간을 너무 써서 늦었다.

그리고 수강신청도 망해서 멘탈이 나가있던터라 미뤘다. ㅎ

 

'나 진짜 이런 문제 못 푸는구나' 깨달은 문제이다.

풀려고 봤을 때 머릿 속이 엄청 복잡해지면서 막막했다.

막 다양한 부분에서 다양한 방법들이 떠오르면서 어떤 방식을 선택해서 풀어야 효율적으로 풀릴지

그리고 그런 방법을 코드상에서 어떻게 구현하면 좋을지 바로 그려지지 않으니 시작을 하지 못했다.

 

예전 수능 공부 할 때, 수학 문제에서도 문제를 어떻게 풀어나가야하는지 생각하는 과정에서

너무 여러가지 방법이 떠오르고 그 방법들 중 어떤걸 선택해야 풀릴지 몰라 건드리지 못했던 적이 많은데 딱 그 모양이다.

그러니까.....풀기 전에 너무 생각이 많다...........

 

첫 번째 풀이

 

def solution(bridge_length, weight, truck_weights):
    from collections import deque
    
    time = 0
    
    bridge = deque()
    
    bridge.append([truck_weights[0], 0])
    truck_weights.pop(0)
    
    while True:
    	#1. 모든 항목에 거리 +1
        for item in bridge:
            item[1] += 1

        #2. 끝에 도달한 트럭이 있다면 popleft
        if bridge[0][1] == bridge_length:
            bridge.popleft()
        
        if len(truck_weights) == 0 and len(bridge) == 0:
            break
            
        bg_sum = 0

        for item in bridge:
            bg_sum += item[0]

        #3. sum + next < limit라면 push
        if len(truck_weights) > 0 and bg_sum + truck_weights[0] <= weight:
            bridge.append([truck_weights[0], 0])
            truck_weights.pop(0)
        
        time += 1
        
    return time+2

 

일단 가장 단순하면서 직관적인 방법이다.

---

다리 위에 있는 트럭의 무게를 합산하고 올라갈 트럭의 무게를 합헤 무게 제한과 비교한다.

그 후 제한을 넘으면 새로운 트럭을 넣지 않고, 제한을 넘지 않으면 새로운 트럭을 넣는다.

다리 위의 트럭은 1초마다 모두 1씩 움직이도록 한다.

다리 끝에 도착한 트럭이 있으면 다리 밖으로 뺀다.

반복

---

 

기본적으로 시간을 업데이트하면서 트럭을 빼고 넣고하므로

시간의 업데이트 사이에 어떤 로직이 어떤 순서로 들어갈지 고민해야했는데

예시 1번을 직접 해보면서 뽑아내었다.

 

  1.  다리 안의 모든 항목 거리 +1 //이를 위해선 트럭 별로 움직인 거리가 따로 들어가야한다.

  2.  끝에 도달한 트럭? -> popleft

  3.  다리 무게 합 + 다음 트럭 무게 < 무게 제한? -> push

  4. 시간 +1

 

이런 순서를 기반으로 잡고 첫 번째 풀이 코드를 짜면서 종료조건이나 정답과의 차이처럼

코드에서 부족한 부분을 채워나갔다.

1번에서 적어두었듯이 트럭 별로 움직인 거리가 따로 기록되어야하므로

queue에 트럭을 넣을 때 [트럭 무게, 거리]의 형태로 추가하고 위의 로직을 따라가도록 짰다.

효율적인 코드는 아니지만 이렇게 잡고 가니까 고민한 시간이 아까울 정도로 코드는 금방 짜지더라.

 

 

두 번째 풀이

 

def solution(bridge_length, weight, truck_weights):
    from collections import deque
    
    time = 0
    
    bridge = deque()
    
    while True:
        #1. 모든 항목에 거리 +1
        for item in bridge:
            item[1] += 1

        #2. 끝에 도달한 트럭이 있다면 popleft
        if len(bridge) != 0 and bridge[0][1] == bridge_length:
            bridge.popleft()
            
        bg_sum = 0

        for item in bridge:
            bg_sum += item[0]

        #3. sum + next < limit라면 push
        if len(truck_weights) > 0 and bg_sum + truck_weights[0] <= weight:
            bridge.append([truck_weights[0], 0])
            truck_weights.pop(0)
        
        time += 1
        
        if len(bridge) == 0 and len(truck_weights) == 0:
            break
        
    return time

 

일단 위 코드에서 문제였던 부분을 2가지를 뽑자면 return 값이 time+2로 따로 수정되어야 한다는 점,
그리고 반복하면 되는 로직을 짠 것과 달리 처음에 deque에 값을 넣어주어야 실행이 가능했다는 점에서

의도하였던 로직과 다르게 수행된 부분이 있다는 것이었다.

우선 return값을 +2를 해줘야하는 문제는 로직이 수행되는 과정에서 time이 업데이트가 되지 않은 부분이 2번 있다는 뜻인데,살펴보니 처음 deque값을 넣으면서 1번, 그리고 종료조건을 체크문이 time+=1보다 위쪽에 있어서 반영되지 않아서 1번

총 2번 업데이트되지 않음을 발견하였다.

둘째로, 처음 deque에 값을 넣어주어야 하는 문제는 

deque로 정의된 bridge가 비었을 때 index range error가 발생하는 것을 방지하기 위해 작성한 코드였고,

#2에 bridge 내부 길이를 체크하는 조건을 추가하여 수정하였다.

 

 

세 번째 풀이 : 리스트 자료형을 사용한 풀이

 

def solution(bridge_length, weight, truck_weights):
    time = 0
    bridge = []
    
    while True:
        #1. 모든 항목에 거리 +1
        for item in bridge:
            item[1] += 1

        #2. 끝에 도달한 트럭이 있다면 popleft
        if len(bridge) != 0 and bridge[0][1] == bridge_length:
            bridge.pop(0)
            
        bg_sum = 0

        for item in bridge:
            bg_sum += item[0]

        #3. sum + next < limit라면 push
        if len(truck_weights) > 0 and bg_sum + truck_weights[0] <= weight:
            bridge.append([truck_weights[0], 0])
            truck_weights.pop(0)
        
        time += 1
        
        if len(bridge) == 0 and len(truck_weights) == 0:
            break
        
    return time

 

두 번째 풀이를 보면서 deque를 import하지 않고도 충분히 구현 가능하겠다는 생각이 들어서

리스트 자료형을 이용해서 코드를 짜보았다.

append나 pop 함수가 리스트 자료형에도 똑같이 있기 때문에 리스트 자료형으로 충분히 동작하였다.

 

---

시간 복잡도

 

가장 이상적인 경우에 O(N^2)인가 싶긴 한데

이상적인 경우 말고는 정확히 계산을 못하겠다. ㅎ

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

카테고리 상으로는 스택/큐에 속하는 문제지만

실제론 피지컬로 코드를 구현해내는 구현 문제에 좀 더 가까운 듯 하다.

이런 문제는 필요한 로직은 어떻게 구성하고 순서는 어떻게 해야하지라고 막 생각이 꼬이는데

처음에 주어진 가장 쉬운 예제를 직접해보면서 필요한 로직을 뽑아내는 과정을 꼭 해봐야하는 것 같다.

일종의 단순화 과정인데 이를 바탕으로 구현하는 방식으로 가면

코드 자체는 비효율적일지라도 생각이 꼬이지 않고 코드를 구현할 수 있기 때문에

망설이는데 시간을 쓰지 않고 코드를 구현할 수 있게 된다.