징검다리 건너기

게시 2024/12/09

By 김동주

13 분읽는 시간

징검다리 건너기

지문을 읽어보면 다음과 같은 내용이 존재합니다.

징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

세 번째 조건을 보자마자 불현듯 징검다리는 연결 리스트의 형태를 띄고 있다는 생각이 들었습니다.

디딤돌이 사라지는 것만 올바르게 구현하여 시뮬레이션 한다면 정답을 구할 수 있을 것으로 보고 문제에 접근을 시도하였습니다.

풀이 논리

시뮬레이션:

숫자가 가장 작은 디딤돌을 선택
- 선택된 디딤돌에 적힌 숫자 만큼의 사람은 건널 수 있다. → 정답 후보로서 기억
디딤돌을 제거
이후의 사람들이 건널 수 있는지 검사.
- 제거한 디딤돌의 앞 뒤로 남아있는 디딤돌의 거리를 계산.
- 두 디딤돌의 거리가 $K$ 보다 크다면, 더 이상 사람이 건너는 것은 불가능하다. → 시뮬레이션 조기 종료
더 이상 남은 디딤돌이 없을 때까지 시뮬레이션 반복.

→ 시뮬레이션 중 발견한 정답 후보 중 가장 큰 값이 정답.

디딤돌의 제거

가령, 디딤돌의 초기 상태가 아래와 같았다면,

graph LR
1((4)) --> 2((3)) --> 3((5))

세 번째 사람이 지나가기 전에는 아래와 같은 상태가 되고, (= 두 번째 사람이 지나간 후)

graph LR
1((2)) --> 2((1)) --> 3((3))

세 번째 사람이 건너간 후에는 두 번째 디딤돌이 무너져 아래와 같은 상태가 됩니다.

graph LR
1((1)) -.-x 2((0)) -.-x 3((2))

더 이상 두 번째 디딤돌을 통해 건너갈 수 없으므로, 아래와 같이 첫 번째 디딤돌과 세 번째 디딤돌의 링크를 다시 연결해주어야 합니다.

graph LR
1((1)) -.-x 2((0)) -.-x 3((2))
1 ---> 3
style 1 stroke-width:4px
style 3 stroke-width:4px

단일 연결리스트와 시간 복잡도

디딤돌의 총 개수를 $N$이라고 해봅시다.

만약 단일 연결 리스트로 풀이를 구현한다면, 제거할 노드를 선택하는 것에 $O(N)$의 시간이 걸립니다. 이 때, 제거할 노드는 가장 작은 숫자가 적힌 디딤돌이 됩니다.

graph LR
HEAD -.-> 0((3)) --> 1((1)) -.-x 2((0)) -.-x 3((2)) --> 4((1))
1 ---> 3

style 1 stroke-width:4px

노드를 제거한 후에는 앞 뒤 노드를 연결해주어야 하는데, 이를 편하게 하기 위해서는 이전 과정에서 제거할 노드의 이전 노드를 기억해두는 테크닉을 사용하거나, 제거할 노드의 이전노드를 다시 탐색해야 하는 번거로움이 있습니다.

총 $N$개의 돌에 대하여 위 과정을 반복해주어야 하므로, 정답을 구하기 위해서는 $O(N^2)$ 시간이 소요되겠네요.

문제의 제한사항에서 $N \leq 200,000$ 이라고 명시되어있으므로, $O(N^2)$ 풀이는 높은 확률로 시간 초과를 받을 것 같습니다.

임의 접근 + 이중 연결리스트

각 디딤돌에 대하여 이전 디딤돌과 다음 디딤돌을 기억하도록 하여 이중 연결리스트를 구현하면 훨씬 간편하게 노드를 제거할 수 있습니다.

graph LR
0((4)) <--> 1((2)) <--> 2((1)) <--> 3((3)) --> 4((2))

파이썬에서는 아래와 같이 간단하게 이중 연결리스트를 구현할 수 있습니다.

  
# doubly linked list
prev = [i-1 for i in range(len(stones)+1)]
next = [i+1 for i in range(len(stones)+1)]

연결리스트 구성에는 $O(N)$의 시간이 소요됩니다.

임의 접근을 편하게 하기 위하여 정점(디딤돌)의 순서$(0..N-1)$를 각 정점를 구분하는 인덱스로 사용하기로 합니다.
prev와 next 마지막에 정점의 개수보다 원소를 하나 더 추가해 준 것은 -1과 len(stones) 번째 인덱스를 접근해도 IndexError가 발생하지 않도록 padding해 준 것입니다.

다음은 정점의 제거입니다. 문제를 푸는 과정에서 정점이 추가되는 일은 없으므로, 정점의 제거는 단순히 전후 노드를 서로 연결해주는 것만으로 충분합니다.

Python에서는 동시 swap이 쉬우므로 아래와 같이 구현해버리면 됩니다.

  
# remove idx-th node
# from: A <-> B <-> C
# to  : A <-------> C
prev[next[idx]], next[prev[idx]] = prev[idx], next[idx]

이제 각 정점의 번호를 각 정점(디딤돌)에 적힌 숫자에 대하여 오름차순 정렬을 합니다.

built-in 함수 sorted()를 사용하여, $O(N \log N)$ 시간에 정렬을 수행할 수 있습니다.

  
idx_asc = sorted(range(len(stones)), key=lambda i: stones[i]) # 방문 순서

이제 아래 그래프와 같이 준비가 되었습니다.

flowchart LR

subgraph stones["디딤돌 (stones[])"]
    direction LR
    A(("stones[0]: 4")) <--> B(("stones[1]: 2")) <--> C(("stones[2]: 1")) <--> D(("stones[3]: 3")) <--> E(("stones[4]: 2"))
end

subgraph order["방문 순서 (idx_asc[])"]
    direction LR
    1(("stones[2]")) --> 2(("stones[1]")) --> 3(("stones[4]")) --> 4(("stones[3]")) --> 5(("stones[0]"))
end

order ~~~ stones

1 -..-> C
2 -.-> B

style stones fill:none,stroke:none

더 이상 건널 수 없는 경우 탐색

다만, 더 이상 징검다리를 건널 수 없는 경우, 시뮬레이션을 중단해야한다는 점이 남았습니다.

앞서, 편의상 정점(디딤돌)의 순서$(0..N-1)$를 각 정점를 구분하는 인덱스로 사용하기로 했으므로, 두 정점의 간격은 두 정점의 번호의 차와 같습니다. 해당 성질을 이용하여 간단하게 검사 로직을 구현할 수 있습니다.

  
# 새로이 벌어진 간격에 대한 검사 (index 번호 이용)
if (next[idx]-prev[idx]) > k:
    # 시뮬레이션 중단
    ...

# 시뮬레이션 계속

시뮬레이션

최종 코드는 앞서 생성한 이중 연결리스트의 생성, 원소 정렬, 순차적인 노드 제거, 그리고 시뮬레이션 지속 가능 여부 검사의 반복입니다.

  
def solution(stones: list, k: int) -> int:
    # doubly linked list
    prev = [i-1 for i in range(len(stones)+1)]
    next = [i+1 for i in range(len(stones)+1)]
    idx_asc = sorted(range(len(stones)), key=lambda i: stones[i])

    ans = 0
    for idx in idx_asc:
        ans = stones[idx]

        # remove idx-th node
        # from: A <-> B <-> C
        # to  : A <-------> C
        prev[next[idx]], next[prev[idx]] = prev[idx], next[idx]

        # 새로이 벌어진 간격에 대한 검사 (index 번호 이용)
        if (next[idx]-prev[idx]) > k:
            break
    return ans

최종 시간 복잡도

이중 연결리스트 구성: $O(N)$
방문 순서 정렬: $O(N \log N)$
시뮬례이션: $O(N)$
- 시뮬례이션 단계 수: $O(N)$
- 시뮬레이션 단계 별: $O(1)$
  - 디딤돌 제거: $O(1)$
  - 종료 조건 검사: $O(1)$

최종 시간 복잡도: $O(N \log N)$

번외

프로그래머스 커뮤니티와 AUSG PS 스터디 활동을 하다보니, 매개변수 탐색으로 접근하신 분들이 생각보다 많다는 것을 느꼈습니다.

매개변수 탐색

매개변수 탐색도 분명 좋은 솔루션입니다. 매개 변수 탐색의 경우, 일반적으로 아래와 같은 로직으로 구성되더군요.

사람 수가 $x$일 때, 모두 건널 수 있는지 검사하는 함수 $\text{validate}(x)$ 정의. $O(N)$
$\text{validate}(x)$에 대하여 매개변수 탐색 수행.
1. $s = 0, e = \max(\text{stones})$ 로 탐색 범위를 초기화.
2. $m = \frac{s+e}{2}$를 구한 뒤, $\text{validate}(m)$ 의 결과에 따라, $s$ 혹은 $e$를 재조정.
3. $s < e$ 인동안 탐색을 계속함.

이 경우, 시간복잡도는 $O(T_\text{validate} \times T_\text{parametric search})$ 입니다. 이 때, 매개변수 탐색의 탐색 범위는 $[0, \max(\text{stones})]$ 이므로, 시간 복잡도는 $O(\log \max(\text{stones}))$ 입니다.

따라서, 최종 시간복잡도를 다시 정리하면 $O(N \log \max(\text{stones}))$ 입니다.

이중 연결 리스트와의 비교

지문에서 제시하는 제한사항은 다음과 같습니다.

$N \leq 200,000$
$\max(\text{stones}) \leq 200,000,000$

두 풀이의 전체 시간복잡도를 비교하면 아래와 같습니다.

이중 연결 리스트: $O(N \log N)$
매개 변수 탐색: $O(N \log \max(\text{stones}))$

비교하면 $O(\log N) \leq O(\max(\text{stones}))$ 이므로, 이중 연결 리스트의 풀이가 조금 더 효율적이라는 것을 알 수 있습니다만, $\log$ 시간대에서의 비교이므로 유의미한 차이는 아닐 것이라는 생각이 듭니다.

두 풀이 모두 좋은 접근 법이니 코딩테스트와 같은 실전에서는 본인에게 있어 구현이 편한 쪽으로 접근하는 것이 유리하겠습니다.