문제 소개
순환(circular) 리스트 nums가 있다고 가정해 보겠습니다. 순환 리스트는 첫 번째 요소와 마지막 요소가 서로 이웃하여 시작과 끝이 연결된 원형 구조를 말합니다. 임의의 인덱스 i에서 출발할 때, nums[i]가 양수이면 nums[i]칸 앞으로 이동하고, 음수이면 그만큼 뒤로 이동합니다. 이때 확인해야 할 것은 길이가 1보다 크면서 경로가 오직 한 방향(앞으로만 또는 뒤로만)으로 진행되는 사이클이 존재하는지 여부입니다.
예를 들어 입력이 nums = [-1, 2, -1, 1, 2]라면 결과는 True입니다. [1 → 3 → 4 → 1]이라는 정방향 경로가 존재하기 때문입니다.
알고리즘 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- n := nums의 크기
- n이 0이면 False 반환
- seen := 크기가 n인 배열을 만들고 0으로 초기화 (방문 여부 추적용)
- nums의 각 요소 x를 x mod n 값으로 변환
- iter := 0으로 초기화
- i를 0부터 n-1까지 반복하며 다음을 수행
- nums[i]가 0이면 다음 반복으로 건너뜀
- iter를 1 증가시키고, pos := True, neg := True, curr := i로 설정
- 다음 과정을 반복 수행
- nums[curr]가 0이 아니고 seen[curr] == iter이면 True 반환 (같은 탐색 내 재방문 → 사이클 발견)
- seen[curr]이 0이 아니면 루프 탈출 (이전 탐색에서 이미 방문한 지점)
- nums[curr] > 0이면 neg := False, 아니면 pos := False
- pos와 neg가 모두 False이면 루프 탈출 (방향이 섞여 유효하지 않음)
- seen[curr] := iter로 표시
- curr := (curr + nums[curr] + n) mod n으로 다음 위치 계산
- nums[curr] == 0이면 루프 탈출
- 모든 반복이 끝나면 False 반환
핵심 포인트
이 알고리즘의 핵심은 seen 배열을 시작점마다 새로 초기화하지 않고 iter 카운터로 방문 시점을 구분한다는 점입니다. 동일한 iter 값으로 표시된 지점을 다시 만나는 순간 사이클이 확인되며, 이 방식 덕분에 전체 탐색 비용을 O(n) 수준으로 유지할 수 있습니다. 또한 파이썬에서 음수의 모듈로 연산(x % n)은 항상 0 이상의 결과를 반환하므로, 순환 리스트에서 뒤로 k칸 이동하는 것은 앞으로 n-k칸 이동하는 것과 같은 효과를 냅니다.
예제 코드
다음 구현을 살펴보면 이해에 도움이 됩니다.
def solve(nums):
n = len(nums)
if n == 0:
return False
seen = [0]*n
nums = [x % n for x in nums]
iter = 0
for i in range(n):
if nums[i] == 0:
continue
iter += 1
pos = True
neg = True
curr = i
while True:
if nums[curr] and seen[curr] == iter:
return True
if seen[curr]:
break
if nums[curr] > 0:
neg = False
else:
pos = False
if not neg and not pos:
break
seen[curr] = iter
curr = (curr + nums[curr] + n) % n
if nums[curr] == 0:
break
return False
nums = [-1, 2, -1, 1, 2]
print(solve(nums))
입력
[-1, 2, -1, 1, 2]
출력
True