프로그래머스 코딩테스트 고득점 Kit : 스택/큐

해당 문제는 프로그래머스에서 제공된 문제입니다.

그다음으로 푼 문제들은 스택/큐 파트 부분이다. 이 부분에서 좀 까다로웠던 문제 하나를 소개하겠다. 내가 풀었던 방식에 대해 설명하고 다른 사람의 풀이 중 괜찮은 풀이 또한 설명하겠다.

[문제 설명]

코딩테스트 연습 - 다리를 지나는 트럭

좀 까다로웠던 문제는 다리를 지나는 트럭이다. 일단 이 문제가 요구하는 게 무엇이고 어떻게 접근해야 되는지 알아보자. 먼저, 이문제가 요구하는 것은 무게, 다리의 길이, 다리의 최대 수용 트럭 무게가 주어진 상황에서 트럭이 순서대로 최단 시간 안에 건널 수 있게 하는 것이다. 즉, 대기 트럭을 순서대로 다리가 수용할 수 있는 트럭의 개수와 무게를 넘어서지 않으면서 다리를 넘게 해야 하는 것이다. 순서대로 이기 때문에, 처음 들어간 트럭이 처음 나가고, 그다음 들어간 트럭이 그다음으로 조건에 맞게 나가면 된다. 즉, 큐를 이용하라는 뜻이다. 여기서 대기 트럭과 다리를 지나가고 있는 순간의 트럭을 저장하는 2개의 큐가 필요하다. 이를 상기시키며 코드를 살펴보자.

---

[문제 풀이]

from collections import deque


def solution(bridge_length, weight, truck_weights):
    check_finished = truck_weights # 종료조건에서 사용하기 위한 초기의 대기 트럭들
    on_bridge = deque() # 다리를 건너고 있는 트럭들을 저장하기 위한 queue
    passed = [] # 다리를 건넌 트럭들을 저장하기 위한 list, 추후에 check_finished와 비교 (종료조건)
    truck_weights = deque(truck_weights) #대기 트럭들 또한 queue로 설정
    total_weight = 0 # 다리의 최대 수용 무게와 비교하기 위한 현재 다리위의 트럭들의 무게 합
    time = 1 # 시간측정
    while True:
    	#초기의 대기 트럭들과 다리를 건넌 트럭들이 같다면 종료
        if passed == check_finished: 
            break
            
        # 대기 트럭이 존재한다면 (대기트럭이 존재하지 않는데 시간측정될 때가 있음)
        if truck_weights: 
            next_truck = truck_weights[0] # 현재 시간에 들어와야 하는 순서의 트럭
            # 다리의 트럭 최대 수용 개수와 무게를 넘지 않는다면
            if len(on_bridge) < bridge_length and total_weight + next_truck <= weight:
                total_weight += next_truck # 무게의 합을 더해주고
                on_bridge.append([truck_weights.popleft(), time])
                # -> 현재 들어와야하는 트럭을 대기 트럭에서 빼고 추후의 시간을 비교 하기 위해
                # 들어왔을 때의 시점과 함께 다리를 건너고 있는 트럭의 queue에 저장
        time += 1 # 시간 측정 +1
        # (현재 다리 위에 있는 트럭중 가장 앞에 있는 트럭이 다리를 다 건너는 시점)
        if time - on_bridge[0][1] == bridge_length: # -> '현재 시간 - 들어온 시점'이 다리의 길이와 동일할 때
            total_weight -= on_bridge[0][0] # 현재 다리 위의 트럭의 무게에서 빠지는 트럭의 무게를 빼줌
            passed.append(on_bridge.popleft()[0]) # 다리를 건넌 트럭의 queue에 저장

    return time

사실 이 문제에서 가장 까다로운 점은 트럭이 들어오고 나가는 시점이다. 이를 어떻게 처리하느냐에 따라 코드들도 다르고 시간복잡도도 다 달라지는 것 같다. 이 부분은 나는 해당 트럭이 들어오면 뒤에 어떤 트럭이 추가되든 말든 다리의 길이만큼의 시간 후에 다리를 다 건넌다 라는 생각을 통해서 현재 시간과 해당 트럭이 들어온 시점의 차이가 다리의 길이와 동일할 때 그 트럭을 passed로 건네주었다. 이렇게 하면 해당 시간에 다리 위에 있는 모든 트럭에 대해서 일일이 빼내 줘야 할지 판단할 필요 없이 트럭을 뺄 수 있다. 또한, 다리 위의 트럭의 무게 합을 sum()으로 구현하지 않고 시간복잡도를 줄이기 위해 그때마다 추가 or 삭제하며 total_weight을 통해 구현했다.

---

[잘못된 풀이]

맨 처음 나는 트럭이 들어오고 나가는 시점을 트럭이 들어옴과 동시에 처리하려고 했다. 즉 반복문 자체를 시간을 기준으로 돌린것이 아닌, 트럭을 기준으로 돌렸다. 그것이 나의 첫 실수였다. 이렇게 되면 내가 구해야 되는 것은 시간이기에 문제를 더 복잡하게 가져가는 것 밖에 되지 않는다. 푸는 도중 결국 머리가 딸려서 처음부터 다시 풀며 시간을 기준으로 반복문을 돌렸다. 

---

[다른 사람의 풀이]

다른 사람들의 풀이 중 인상 깊었던 것은 차피 순서대로 하기에 queue로 구현하지 않고 list를 reverse하여 stack으로 구현하여 시간복잡도를 줄이는 케이스도 괜찮았던 것 같다. 또한, 시간을 기준으로 판단하지 않고 직접 다리 위의 빈 곳을 0으로 채우고 빼가며 문제 설명 그대로 따라간 풀이도 괜찮았다. (이 부분은 생각은 했지만 시간 복잡도에서 비효율적인 것 같아 다른 방법을 택했으나 생각보다 시간 복잡도가 나쁘지 않았었나 보다)

---

[마무리]

요즘 드는 생각은, 이 문제를 나중에 다시 푼다면 더 빠르게 효율적으로 풀 수 있을까? 라는 생각이 든다. 그만큼 지금 내 공부 방식에 회의가 든다는 뜻이다. 많은 문제를 푸려고 하기보다는 한 문제를 풀더라도 이 문제를 온전히 내 것으로 만들고 넘어가는 게 더 좋은 공부방법일 것 같다는 생각을 한다.