코딩 테스트/LeetCode
1752. Check if Array Is Sorted and Rotated (배열이 정렬되고 회전되는지 확인)
포카리tea
2024. 10. 8. 16:42
배열 nums가 주어지면 배열이 오름차순으로 정렬된 다음 몇 개의 위치(0 포함)를 회전시킨 경우 true을 반환합니다. 그렇지 않으면 false을 반환합니다.
원본 배열에 중복이 있을 수 있습니다.
Notes: 배열 A를 x 위치로 회전하면 A[i] == B[(i+x) % A.length]와 같은 길이의 배열 B가 되며, 여기서 %는 모듈로 연산입니다.
예시 1:
입력: nums = [3,4,5,1,2]
출력: true
설명: [1,2,3,4,5]가 원래 정렬된 배열입니다.
배열을 x = 3 위치만큼 회전하여 값 3의 요소에서 시작할 수 있습니다: [3,4,5,1,2].
예시 2:
입력: nums = [2,1,3,4]
출력: false
설명: 회전하면 nums를 만들 수 있는 정렬된 배열이 없습니다.
예시 3:
입력: nums = [1,2,3]
출력: true
설명: [1,2,3]가 원래 정렬된 배열입니다.
배열을 x = 0 위치(즉, 회전 없음)로 회전하여 nums를 만들 수 있습니다.
조건:
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
정답:
public class Solution {
public bool Check(int[] nums) {
var numsSort = nums.OrderBy(n => n).ToArray();
var minIndexArray = FindAll(nums, nums.Min());
foreach (var minIndex in minIndexArray)
{
int[] numsCopy = new int[nums.Length];
for (int i = 0; i < nums.Length; i++)
{
numsCopy[i] = nums[(i + minIndex) % nums.Length];
}
if (numsSort.SequenceEqual(numsCopy))
{
return true;
}
}
return false;
}
public int[] FindAll( int[] nums, int value )
{
var result = new List<int>();
int pos = 0;
for (int i = 0; i < nums.Count(n => n == nums.Min()); i++)
{
pos = nums.ToList().IndexOf(nums.Min(), pos);
result.Add(pos);
pos += 1;
}
return result.ToArray();
}
}
해설: 이게 Easy 문제인가 싶을정도로 조건이 많이 붙어서 까다로웠는데 우선 numsSort를 생성합니다.
해당 변수는 회전했을 때 정상적으로 정렬되어있는지 확인하기 위한 변수이기 때문에 해당 변수 배열과 동일하다면 정상적으로 정렬되어있는 것으로 판단하여 true를 return합니다.
그리고 동일한 값이 들어가 있을 수 있으므로 오름차순으로 정렬을 할 수 있도록 FindAll에서 최소값의 위치를 모두 찾습니다.
최소값의 위치에 따라 numsCopy에 회전시킨 배열을 넣어주고 numsSort와 비교합니다.
최소값의 위치 모두에서 해당 작업을 반복하고 만약 없다면 false를 return합니다.