99클럽 코테 스터디 2일차 TIL - 반복 학습의 힘

문제 1 - 다리를 지나는 트럭 문제링크

 

오늘 배운 점

복습의 힘은 대단하다.

이는 일반적인 공부에만 적용되는 것이 아니라 코딩테스트 문제를 풀 때도 마찬가지로 적용된다.

변수의 초깃값을 제대로 설정하는 건 매우 중요하고 때때로는 까다롭다.

이러한 까다로움은 배열의 인덱스를 정확히 설정하는 것과 유사하다.

 

과정

이 문제는 지금까지 총 3번 마주쳤다.

첫번째는 문제 이해를 못해서 넘어갔고,

두번째엔 여러번의 제출을 통해 엣지케이스들을 처리하면서 통과했다.

오늘은 아는 문제라는 걸 깨닫고 머리속으로 어떤 식으로 로직을 짜야 할지 구상한 후 바로 그대로 코드를 짜고 제출을 했고 바로 통과했다. 

 

첫번째로 마주쳤을 때 문제 이해가 어려웠던 이유는 위 그림에 있다.

위 그림에서 경과시간이 1~2 이렇게 되어있는 건 트럭이 1초에서 2초 사이에 다리로 진입하는 모습이 상상되면서 지금까지 A->B같이 연속적이지 않고 atomic한 상태로 진행되는 코드를 작성해왔기 때문에 문제풀이에 대해 감이 잡히지 않았던 기억이 있다.

 

연속적으로 트럭이 이동하는 모습을 상상하지 않고,

트럭이 매 초마다 순간이동하며 앞으로 나아간다고 상상하며 코드를 작성했다.

"""
    1초마다 다리에 있는 트럭은 1씩 전진할 수 있다.
    다리에는 최대 weight만큼의 트럭이 있을 수 있다.
    트럭 웨이트 빌 때까지, 
    1. 다리에 있는 모든 트럭 위치 + 1
    2. 빠져나갔으면 pop
    3. 다리 총 무게 판단 후 트럭 넣을 수 있으면 넣기.
"""
from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    bridge = deque()
    crossed = 0
    loads = 0
    idx = 0
    time = 0
    while crossed < len(truck_weights):
        # 다리에 있는 트럭 이동
        for truck in bridge:
            truck[1] += 1
        
        # 맨 앞 트럭 다리 탈출했나 확인
        if bridge and bridge[0][1] > bridge_length:
            crossed += 1
            loads -= bridge[0][0]
            bridge.popleft()
            
        # 다리에 트럭 추가할 수 있으면 추가
        if len(bridge) < bridge_length and idx < len(truck_weights) and loads + truck_weights[idx] <= weight:
            loads += truck_weights[idx]
            bridge.append([truck_weights[idx], 1])
            idx += 1
        time += 1
    
    return time

 

오늘까지 두 번 푼 문제지만, 아예 고려할 게 없었던 건 아니었다.

1. 다리에 있는 트럭을 움직이는 것과 다리에 트럭을 추가하는 것 중 무얼 먼저 실행해야 할 지 고민했다.

고민 결과, 다리에 있는 트럭이 먼저 움직여야 한다고 판단했다. 트럭을 다리에 옮긴 후 다리에 있는 트럭을 이동하면 방금 다리에 올라간 트럭은 2초에 해당하는 움직임을 하는 것이기 때문이었다.

그래서, 시뮬레이션 문제를 풀 때는 개별 로직들을 정확한 순서대로 실행되도록 정렬하는게 중요하다.

 

2. time 초기값을 0으로 할지 1로 할지도 생각의 과정을 거쳤다.

결정하는 근거로 아주 작은 케이스를 상상했다.

다리 길이가 0이고, 트럭은 1초에 1만큼 움직이며, 가장 이른 순서의 트럭은 다리 외부에 있다. 나는 뒤 돌아보고 있다가 1초가 지나고 다리 다리를 보면 해당 트럭은 다리의 첫 지점에 위치해 있을 것이다. 다리 길이가 0이기 때문에, 이 순간 트럭은 다리를 탈출한 상태이다. 지금까지 1초 지났으므로 트럭은 다리를 1초만에 탈출했다. 따라서 time의 초깃값은 0이 맞다.

물론 코드를 정확히 작성했다면 1로 초기화해보았을 때 모든 결과값이 정답보다 1 높았을 것이므로 0으로 초기화하면 된다는 걸 바로 알테지만, 찍어서 맞추는 것 같아 하지 않았다.

 

결론

복습의 힘은 대단하다.

이는 일반적인 공부에만 적용되는 것이 아니라 코딩테스트 문제를 풀 때도 마찬가지로 적용되었다.

그리고, 변수의 초깃값을 제대로 설정하는 건 매우 중요하고 때때로는 까다롭다.

이러한 까다로움은 배열의 인덱스를 정확히 설정하는 것과 유사하다.