탐험가가 북서남동(반시계방향으로) 주어진 배열의 길이만큼씩 계속 움직인다. 전부 움직이는 동안 한번이라도 본인의 경로를 밟는 경로가 있을까?
ex ) 2 1 1 2 >> cross(1)
1 2 3 4 >> not cross(0)
이건 빼박 성질탐구 문제네..
뭐 나이브하게는 경로를 기록해 두면서 밟는지 체크할 수 있겠지만, 메모리 사용이 과다하고
정답 요구사항은 싱글 패스, O(1) 메모리이므로 결국 성질탐구 뿐
대충 두가지 방법이 있는데, 안으로 줄어드는 경우와 밖으로 확산하는 경우가 있다. 두 경우에 대해 계속적으로 성립하는지 확인해 나가야 한다.
// There are only two patterns when cross can happen,
// one involves four moves another involves six moves.
// Checking for this patterns is sufficient.
// C#
static void Main(string[] args)
{
//double[] n = new double[] { 2, 2, 2, 1 }; // No cross
//double[] n = new double[] { 2, 2, 2, 2 }; // Cross
//double[] n = new double[] { 3, 2, 2, 3 }; // Cross
//double[] n = new double[] { 3, 3, 2, 2, 3 }; // Cross
//double[] n = new double[] { 2, 2, 4, 5, 1, 4 }; // No Cross
//double[] n = new double[] { 2, 2, 4, 5, 3, 4 }; // Cross
//double[] n = new double[] { 1, 2, 4, 5, 1, 4 }; // No Cross
double[] n = new double[] { 0.5, 2, 2, 4, 5, 3, 4, 0.5 }; // Cross
for (int i = 0; i < n.Length; i++)
{
if (i >= 3 &&
n[i] >= n[i - 2] &&
n[i - 1] <= n[i - 3])
{
Console.WriteLine("Cross Detected, pattern #1");
return;
}
if (i >= 5 &&
n[i] >= n[i - 2] - n[i - 4] &&
n[i - 2] >= n[i - 4] &&
n[i - 1] >= n[i - 3] - n[i - 5] &&
n[i - 3] >= n[i - 5])
{
Console.WriteLine("Cross Detected, pattern #2");
return;
}
}
Console.WriteLine("No Cross");
}