[99클럽/코딩테스트 챌린지] [프로그래머스] 다리를 지나는 트럭

처음에 문제를 보고서, 당황했던게..

시간이 지남에 따라 트럭들이 1씩 밀린다는걸 문제로 바로 알 수가 없었다.

그리고 다리의 길이 자체도.. 큐에 담을 수 있는 트럭 갯수와 같다는 것도 바로 알 수가 없어서, 풀이가 막막했다(..)

 

이 문제는 큐로 풀었는데, 풀고나서 다른 분들 풀이를 보니 수학으로 푸신 분도 있고, 같은 큐 라도 내부 구현에 있어서 어떻게 하시는지 좀 공부가 되었다.

 

이게 나는 처음에 직관적으로 큐를 이용해 풀다가 큐가 [0, 0] 이 되는 상황을 피할 수가 없어서

일단 트럭을 전진 시킨 다음에, 나중에 큐의 마지막 자리에다가 상황에 따라 다음 트럭을 얹는 식으로 만들었다.

 

테스트케이스 1의 큐의 변화

코드설명
처음으로 큐 초기화 (for문 밖)	0	0
트럭들 중 최초 진입	7	0
다음차 진입불가 (무게제한)	0	7
밀린 다음차 진입	4	0
다음차 바로 진입	5	4
다음차 진입불가 (무게제한)	0	5
밀린 다음차 진입	6	0
후속차 없이 진행	0	6
전부 다 빠져나감	0	0

 

여기서 중요한것은, 다음차가 진입하지 못하는 때를 구별해서 그땐 그냥 있는 트럭 진행만 시키고, 밀린걸 다음에 처리한다는 것이다.

독해력이 딸려서 그런지 이거 이해를 못해서 몇시간을 날렸다(...)

별도 테스트케이스 의 큐의 변화

문제를 풀다가 테스트케이스 실패가 뜨는 경우가 있었는데, 반례를 열심히 고민해본 결과

[새 트럭]~~공백~~[기존트럭]  --> 결과적으로 이렇게 큐가 밀릴 수 있다는걸 고려 못하고 기존 트럭이 다 나간 이후에야 새 트럭이 들어가는 상황이었다.

 

나는, 먼저 일단 0를 appendleft 해서 으로 기존 트럭을 진행 시킨 다음에, 나중에 새로 진입할 트럭에 대한 처리를 하는 식으로 해결했는데

다른분들 코드를 보니 거꾸로..일단 맨 마지막 큐를 pop 한 다음에 새로 트럭을 진입하는 식으로 만들어 두셨다.

 

내가 짠 테스트 케이스는 무게 2, 트럭댓수 5, 트럭리스트[1,1,1] 이었다.

1	0	0	0	0
1	1	0	0	0
0	1	1	0	0
0	0	1	1	0
0	0	0	1	1
** 1	0	0	0	** 1
0	1	0	0	0
0	0	1	0	0
0	0	0	1	0
0	0	0	0	1

 

이런식으로 큐가 진행되도록 만들어줘야 한다.

그리고, 시간초과가 나는 부분이 있길래 sum 함수 대신에 입출력 할때마다 따로 처리를 해줬다.

 

from collections import deque
def solution(bdg_l, bdg_w, truck_weights):
    last_item = truck_weights[len(truck_weights) - 1]
    passing = deque([0 for _ in range(bdg_l)],maxlen=bdg_l)
    passing.appendleft(truck_weights.pop(0))
    time = 1
    next_item = 0
    total = passing[0]
    while(len(passing) > 0):
        next_item = truck_weights[0] if(len(truck_weights) > 0) else 0
        # 만약 넘친다면 총합에서 빼기 위함
        if(len(passing) == bdg_l):
          total -= passing[bdg_l - 1]
        # 일단 한 칸 진행
        passing.appendleft(0)
        # 다음차 바로 진입
        if(total + next_item <= bdg_w):
          passing[0] = next_item
          total += next_item
          if(len(truck_weights) > 0): truck_weights.pop(0)
        else:
          passing[0] = 0
        if(total == 0 and 0 != next_item):
          passing[0] = next_item
          total += next_item
          if(len(truck_weights) > 0): truck_weights.pop(0)
        time += 1
        if(total == 0): break
    return time