문제 소개
숫자로 이루어진 리스트 nums가 주어지고, 우리는 현재 nums[0] 위치에 서 있다고 가정해 봅시다. 각 단계에서 현재 인덱스 i로부터 다음 세 가지 이동 중 하나를 선택할 수 있습니다.
- i + 1로 이동 (한 칸 앞으로)
- i - 1로 이동 (한 칸 뒤로)
- nums[i] == nums[j]를 만족하는 임의의 인덱스 j로 점프
이때 리스트의 마지막 인덱스까지 도달하는 데 필요한 최소 단계 수를 구하는 것이 목표입니다.
예를 들어 입력이 nums = [4, 8, 8, 5, 4, 6, 5]라면 출력은 3이 됩니다. 그 이유는 다음과 같습니다.
- 인덱스 0과 인덱스 4는 값이 모두 4이므로, 인덱스 0에서 인덱스 4로 바로 점프할 수 있습니다.
- 그다음 한 칸 뒤로 이동하여 인덱스 3에 도착합니다.
- 마지막으로 인덱스 3과 인덱스 6은 값이 모두 5이므로, 인덱스 6으로 점프하여 끝에 도달합니다.
총 3번의 이동만으로 목표 지점에 도달할 수 있습니다.
해결 접근 방식: 너비 우선 탐색(BFS)
이 문제는 그래프 탐색 관점에서 바라보면 효율적으로 해결할 수 있습니다. 각 인덱스를 노드로 생각하면, 인접한 노드는 i±1과 같은 값을 가진 인덱스들입니다. 시작점에서 목표점까지의 최단 거리를 구하는 문제이므로 BFS(너비 우선 탐색)가 적합합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- pos: 값별 인덱스 목록을 저장할 빈 맵(딕셔너리)을 생성합니다.
- nums의 각 인덱스 i와 값 n에 대해, i를 pos[n]의 끝에 추가합니다.
- n := nums의 길이로 설정합니다.
- visited: 크기가 n인 리스트를 만들고 모두 False로 초기화한 뒤, visited[0]을 True로 설정합니다.
- 큐(q)가 비어 있지 않은 동안 다음을 반복합니다.
- (u, d) := 큐의 왼쪽 요소를 꺼내고 제거합니다.
- u가 n - 1과 같다면 d를 반환합니다.
- pos[nums[u]]의 모든 원소와 [u - 1, u + 1]의 각 v에 대해, 0 <= v < n이고 방문하지 않았다면 visited[v]를 True로 표시하고 큐에 (v, d + 1)을 추가합니다.
- 처리가 끝나면 pos[nums[u]]를 삭제합니다. 같은 값을 가진 인덱스들을 반복해서 순회하는 것을 방지하여 성능을 크게 향상시키는 핵심 최적화입니다.
구현 예제
아래 파이썬 코드로 위 알고리즘을 확인해 보겠습니다.
class Solution:
def solve(self, nums):
from collections import defaultdict, deque
pos = defaultdict(list)
for i, n in enumerate(nums):
pos[n].append(i)
q = deque([(0, 0)])
n = len(nums)
visited = [False] * n
visited[0] = True
while q:
u, d = q.popleft()
if u == n - 1:
return d
for v in pos[nums[u]] + [u - 1, u + 1]:
if 0 <= v < n and not visited[v]:
visited[v] = True
q.append((v, d + 1))
del pos[nums[u]]
ob = Solution()
nums = [4, 8, 8, 5, 4, 6, 5]
print(ob.solve(nums))
입력
[4, 8, 8, 5, 4, 6, 5]
출력
3
마무리
이 풀이의 시간 복잡도는 O(N)입니다. BFS가 각 인덱스를 최대 한 번씩만 방문하고, 같은 값 그룹을 한 번 처리한 후에는 맵에서 삭제하기 때문입니다. 만약 del pos[nums[u]] 라인을 생략하면 같은 값을 가진 인덱스들을 매번 다시 순회하게 되어 최악의 경우 O(N²)까지 느려질 수 있으므로, 이 최적화가 실질적인 성능 차이를 만든다는 점을 기억해 두면 좋습니다.