581. Shortest Unsorted Continuous Subarray

배열이 하나 주어집니다.

 

이 배열은 정렬이 된 배열일 수도 있고, 안되어 있는 배열일 수도 있습니다.

일 수도 있고, 아닐 수도 있습니다.

그렇다면, 이 주어진 배열을 정렬된 배열로 바꾼다면 !? 어느 부분을 바꿔야할까요? 그렇다면 그 바꾸는 부분의 길이는 몇이 될까요 !?

 

를 물어보는 문제입니다.

 

TestCase 하나를 보시죠.

 

[2, 6, 4, 8, 10, 9, 15]

 

멀쩡해보이는 이 배열, 안을 들여다보면 뒤죽박죽, 엉망진창입니다.

 

이 배열을 멀쩡히 정렬된 배열로 만드려고 한다면 1번 ~ 5번 인덱스까지를 정렬하면 됩니다. 즉, 길이는 5가 됩니다.

 

그렇다면 이 문제 어떻게 풀 수 있을까요?

---

1. max / min 함수를 활용하자.

 

저희가 사용하는 언어 Python, 이 Python에는 max, min 함수가 내장되어 있습니다. 배열을 때려 넣으면 최댓값, 최솟값을 뱉어내는 고마운 함수죠.

 

사실 배열이 정렬되어 있다면, 배열의 제일 오른쪽은 제일 큰 수, 제일 왼쪽은 제일 작은 수가 될 것입니다. 이를 이용했습니다.

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s=0
        e=len(nums)-1
        
        while s <= e and min(nums[s:e+1]) == nums[s]:
            s+=1
        while s <= e and max(nums[s:e+1]) == nums[e]:
            e-=1
        
        return e-s+1

제일 왼쪽이 최솟값이 아닐 때까지, 제일 오른쪽이 최댓값이 아닐 때까지를 비교하면서 마지막엔 그 길이를 구하면 성공적으로 문제를 풀 수 있습니다.

성공적..?

LeetCode의 넓은 아량 덕분에 3초가 넘는 제 코드가 Accepted 됐습니다. 한국의 많은 Judge 사이트와는 사뭇 다르군요.

 

솔직히 3초, 알고리즘 문제 푸는 사람이 3초로 통과됐다고 말하면 동네 창피해서 밖에 못 돌아다닙니다.

 

그래서 다른 풀이 방법을 고민해보았습니다.

---

2. 역전되는 수의 위치를 찾자.

 

배열을 순회하는데 갑자기 정렬이 안되고 역전되는 수가 있을겁니다. 그 때를 기억하는 것이 제 새로운 방법의 Key Point 입니다.

 

단, 이를 이용하려면

 

--> 이 방향으로 순회할 떈 그 당시 최댓값보다 작은 수가 나오면, 그 index를 체크하고,

<-- 이 방향으로 순회할 땐 그 당시 최솟값보다 큰 수가 나오면, 그 index를 체크합니다.

 

그러면 역전되는 마지막 순간이 기록되는거니까, 그 사이의 거리를 구하면 문제를 해결할 수 있습니다.

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max = -float('inf')
        min = float('inf')
        
        idx1 = -1
        idx2 = -1
        
        for idx, val in enumerate(nums):
            if max < val:
                max = val
            elif val < max:
                idx1 = idx
        
        for idx, val in enumerate(nums[::-1]):
            if min > val:
                min = val
            elif min < val:
                idx2 = idx
        
        if idx1 == -1:
            return 0
        
        return idx1 - (len(nums) -idx2 -1) + 1

편-안-

---

이상 581. Shortest Unsorted Continuous Subarray였습니다.