581. Shortest Unsorted Continuous Subarray c++ 문제

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/

Shortest Unsorted Continuous Subarray - LeetCode

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

정수 배열 nums가 주어지면 이 하위 배열을 오름차순으로만 
정렬하면 전체 배열이 오름차순으로 정렬되는 하나의 연속 하위 배열을 찾아야 합니다.
가장 짧은 하위 배열을 반환하고 길이를 출력합니다.

 

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in
ascending order to make the whole array sorted in ascending order.

Example 2:

Input: nums = [1,2,3,4]
Output: 0

Example 3:

Input: nums = [1]
Output: 0

 

Constraints:

• 1 <= nums.length <= 104
• -105 <= nums[i] <= 105

 

Follow up: Can you solve it in O(n) time complexity?

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
    
        if(nums.size()==0){
            return 0;
        }
        
        int idx = 0;
        int idx2 = nums.size()-1;
        int right = nums.size();
        int maxNum = nums[0];
        int left = 0;
        int minNum = nums[right-1];
        
        while(idx <= nums.size()&& idx2 >= 0){
            if(nums[idx] < maxNum){
                right = idx;
            }
            maxNum = max(maxNum, nums[idx]);
            idx++;
            
            if(nums[idx2] > minNum){
                left = idx2;
            }
            minNum = min(minNum,nums[idx2]);
            idx2--;
            
        }
        if(right == nums.size() && left == 0){
            return 0;
        }
        return right - left + 1;
    }
};

 

굉장히 이해 안 가는 문제였다 문제 풀이 설명을 듣고 풀었는데도 굉장히 오래 걸렸다 조건식을 작성하는데에 시간이 많이 걸린 문제였다.

큰수작은수를 구별해야 하는 것이면 min max로 쉽게 찾았겠지만 ....

왼쪽 시작 이후 값이 커지다 작아지다가 커지는 저점 idx와 오른쪽 시작 이후 값이 작아졌다 늘어났다 작아지는 고점 idx를 찾는 조건을 적는 것이 어려웠다.

저러한 방식이 문제의 난이도를 확 올린 느낌이다 timecomplexity까지 신경쓰다 보니 확실히 더 힘들었다.

마지막 return right - left +1; 에서 배열을 idx니 +1을 해주어야 하는데 그것을 생각하지 못해 여기서 또한번 많은 시간을 사용하였다.

 

운영중인 카톡방입니다.

https://open.kakao.com/o/gsMhUFie

C/C++/C# 언리얼/유니티 /질문