LeetCode : 581. Shortest Unsorted Continuous Subarray

 

문제)

정수 배열 nums가 주어졌을 때, 배열 전체를 비내림차순으로 정렬하기 위해

비내림차순으로 정렬해야 하는 하나의 연속적인 부분 배열을 찾으시오.

이와 같은 부분 배열 중 가장 짧은 부분 배열을 찾아서 그 길이를 반환하시오.

 

문제 난이도 : 중

 

소요시간 및 풀이)

        int left = 0;
        int right = 1;

        while (right < nums.size() && left < nums.size())
        {

            for (int i = 0; i < nums.size(); i++)
            {
                if (nums[left] < nums[right])

 

이런 느낌으로 접근했었는데,

이렇게 푸는게 아니라 배열의 두 끝에서 정렬이 어긋난 부분을 찾아야 한다.

왼쪽과 오른쪽에서 처음으로 정렬이 어긋나는 곳을 찾아서,

[왼쪽~오른쪽] 범위의 부분 배열에서 최대값과 최소값을 찾아서 

최소값보다 큰 값이 포함되도록 왼쪽 경계를 확장,

최대값보다 작은 값이 포함되도록 오른쪽 경계를 확장해주면 된다.

 

소요 시간 : 못 품

 

정답 코드

    int findUnsortedSubarray(std::vector<int>& nums) 
    {
        int n = nums.size();
        int left = 0;
        int right = n - 1;

        // 왼쪽에서 첫 번째로 정렬이 어긋난 요소 찾기
        while (left < n - 1 && nums[left] <= nums[left + 1]) 
        {
            left++;
        }

        // 배열이 이미 정렬된 경우
        if (left == n - 1)
            return 0;

        // 오른쪽에서 첫 번째로 정렬이 어긋난 요소 찾기
        while (right > 0 && nums[right] >= nums[right - 1])
        {
            right--;
        }

        // 부분 배열 nums[left:right]의 최대값과 최소값 찾기
        int subarray_min = *std::min_element(nums.begin() + left, nums.begin() + right + 1);
        int subarray_max = *std::max_element(nums.begin() + left, nums.begin() + right + 1);

        // 부분 배열의 최소값보다 큰 값이 포함되도록 왼쪽 경계 확장
        while (left > 0 && nums[left - 1] > subarray_min)
        {
            left--;
        }

        // 부분 배열의 최대값보다 작은 값이 포함되도록 오른쪽 경계 확장
        while (right < n - 1 && nums[right + 1] < subarray_max) 
        {
            right++;
        }

        return right - left + 1;
    }