코딩 테스트/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합니다.