문제 소개
n개의 숫자로 이루어진 배열 x가 있다고 가정해 보겠습니다. 우리는 점 (0, 0)에서 출발하여 x[0]만큼 북쪽으로, x[1]만큼 서쪽으로, x[2]만큼 남쪽으로, x[3]만큼 동쪽으로 이동하며, 이후에도 같은 패턴으로 매 이동마다 방향을 반시계 방향으로 회전시켜 나갑니다. 이때 O(1)의 추가 공간만 사용하고 단 한 번의 순회(one-pass)로 경로가 자기 자신과 교차하는지 여부를 판별하는 알고리즘을 설계해야 합니다.
예를 들어 배열이 [3, 4, 2, 5]라고 한다면, 이동 경로는 다음 그림과 같습니다.
위 경우 마지막 이동이 기존 경로와 겹치게 되므로 결과는 true입니다.
접근 방법
이 문제의 핵심은 이동 거리의 변화 추세를 관찰하는 것입니다. 거리가 계속 증가하는 동안에는 나선형으로 바깥쪽으로 퍼져나가기 때문에 교차가 발생하지 않지만, 증가하다가 감소로 전환되는 지점에서 교차 가능성이 생깁니다. 해결 과정은 다음과 같습니다.
- 경계 처리를 위해 배열 x의 맨 앞에 0을 네 개 삽입합니다.
- n := x의 크기, i := 4로 초기화합니다.
- i < n이고 x[i] > x[i - 2]인 동안 i를 1씩 증가시킵니다. (거리가 증가하는 구간을 건너뜁니다)
- 루프 종료 후 i == n이라면 거리가 끝까지 계속 증가했다는 의미이므로 false를 반환합니다.
- 만약 x[i] >= x[i - 2] - x[i - 4]라면, 다섯 번째 변이 첫 번째 변과 만나는 특수한 경우이므로 x[i - 1] -= x[i - 3]으로 값을 조정합니다.
- i를 1 증가시킨 뒤, i < n이고 x[i] < x[i - 2]인 동안 i를 1씩 증가시킵니다. (거리가 감소하는 구간을 건너뜁니다)
- 마지막에 i != n이라면 감소 구간 도중 다시 증가로 전환된 지점이 존재한다는 뜻이므로 true를 반환합니다.
예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
x.insert(x.begin(), 4, 0);
int n = x.size();
int i = 4;
for(; i < n && x[i] > x[i - 2]; i++);
if(i == n) return false;
if (x[i] >= x[i - 2] - x[i - 4]) {
x[i - 1] -= x[i - 3];
}
for (i++; i < n && x[i] < x[i - 2]; i++);
return i != n;
}
};
main(){
Solution ob;
vector<int> v = {3,4,2,5};
cout << (ob.isSelfCrossing(v));
}
입력
{3,4,2,5}
출력
1
출력값 1은 경로가 자기 자신과 교차함을 의미합니다. 이 알고리즘은 배열을 한 번만 순회하고 상수 개의 변수만 사용하므로, 시간 복잡도 O(n), 공간 복잡도 O(1)의 조건을 만족합니다.