문제 개요
양수와 음수 정수로 구성된 원형 배열 nums가 있다고 가정해 보겠습니다. 특정 인덱스의 값 k가 양수라면 앞으로 k칸 이동하고, 음수(-k)라면 뒤로 k칸 이동합니다. 배열이 원형(circular)이므로 마지막 요소의 다음 요소는 첫 번째 요소가 되고, 첫 번째 요소의 이전 요소는 마지막 요소가 됩니다.
목표는 nums 안에 루프(사이클)가 존재하는지 판별하는 것입니다. 여기서 유효한 사이클은 시작과 끝이 같은 인덱스여야 하며, 길이가 1보다 커야 합니다. 예를 들어 입력이 [2,-1,1,2,2]라면 인덱스 0 → 2 → 3 → 0으로 이어지는 길이 3의 사이클이 존재하므로 결과는 true입니다.
해결 접근 방식
이 문제는 플로이드 순환 감지(Floyd's Cycle Detection) 기법, 흔히 '토끼와 거북이' 알고리즘이라고 불리는 방식으로 효율적으로 해결할 수 있습니다. 느린 포인터(slow)는 한 칸씩, 빠른 포인터(fast)는 두 칸씩 이동시켜 두 포인터가 만나는지를 확인합니다. 또한 한 번 탐색한 경로는 0으로 마킹하여 중복 탐색을 방지함으로써 전체 시간 복잡도를 O(n)으로 유지합니다.
구체적인 단계는 다음과 같습니다.
- n := nums의 크기
- n < 2이면 false 반환
- i를 0부터 n-1까지 순회하며 nums[i] := nums[i] mod n 수행
- i를 0부터 n-1까지 순회:
- nums[i] == 0이면 다음 반복으로 건너뜀(continue)
- slow = i, fast = i로 초기화
- nums[slow] × nums[fast] > 0 이고 nums[next(fast)] × nums[slow] > 0 인 동안 반복:
- slow = next(slow)
- fast = next(next(fast))
- slow == fast이면:
- slow == next(slow)이면 루프 탈출 (길이 1짜리 사이클은 무효)
- true 반환
- x := nums[i], slow := i
- nums[slow] × x > 0 인 동안:
- temp := next(slow)
- nums[slow] := 0 (방문 처리)
- slow := temp
- false 반환
아래 구현 예제를 통해 더 자세히 살펴보겠습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int next(vector<int>& nums, int i){
int n = nums.size();
return (n+nums[i]+i)%n;
}
bool circularArrayLoop(vector<int>& nums) {
int n = nums.size();
if(n < 2) return false;
for(int i = 0; i < n; i++)nums[i] %= n;
for(int i = 0; i < n; i++){
if(nums[i] == 0) continue;
int slow = i;
int fast = i;
while(nums[slow] * nums[fast] > 0 && nums[next(nums, fast)] * nums[slow] > 0){
slow = next(nums, slow);
fast = next(nums, next(nums, fast));
if(slow == fast){
if(slow == next(nums, slow))
break;
return true;
}
}
int x = nums[i];
slow = i;
while(nums[slow] * x > 0){
int temp = next(nums, slow);
nums[slow] = 0;
slow = temp;
}
}
return false;
}
};
main(){
vector<int> v = {2,-1,1,2,2};
Solution ob;
cout << (ob.circularArrayLoop(v));
}
코드 핵심 포인트
- next 함수: (n + nums[i] + i) % n 공식을 사용해 음수 값으로 뒤로 이동할 때도 배열 범위를 벗어나지 않는 올바른 인덱스를 계산합니다.
- 방향 일관성 검사: nums[slow] × nums[fast] > 0 조건은 두 포인터가 모두 같은 방향(둘 다 양수 또는 둘 다 음수)으로만 이동하는 유효한 사이클인지 확인합니다.
- 길이 1 사이클 제외: slow == next(slow)인 경우, 즉 자기 자신으로 되돌아오는 길이 1의 사이클은 조건에 맞지 않으므로 제외합니다.
- 방문 마킹: 탐색이 끝난 경로의 값을 0으로 설정해 같은 경로를 다시 검사하지 않도록 하여 성능을 최적화합니다.
입력
[2,-1,1,2,2]
출력
1
출력값 1은 true를 의미하며, 배열에 길이 3의 유효한 사이클이 존재함을 나타냅니다.