[LeetCode] 153. Find Minimum in Rotated Sorted Array / 튜닝의 끝은 순정이다

 
 

 
 
 
튜닝의 끝은 순정이라는 말이 있다.
그리고 이 말은 단순 자동차 문화에 국한되는 말이 아닐 것이다.
 
그 분야가 게임이든, 운동이든, 공부이든 결국 정상에 이르는 사람들은
화려한 겉기술보다, 그 안을 움직이는 본질적 구조를 보려는 사람들이라고 믿고 있다.
 
복잡한 기술과 수많은 방법론도 결국은 소수의 핵심 원리 위에 쌓여있기 때문이다.
 
 

'순정'이라는 건 아무것도 하지 않은 상태가 아니라,
수많은 시행착오와 튜닝 끝에 남는 본질에 가까운 것이라 생각한다.

 

---

 
 
 

Find Minimum in Rotated Sorted Array - LeetCode

 
 
 
 
처음 이 문제를 보면 당황스럽다.
 
N개의 배열 중 최소값을 구하면 되는데, O(logN) 비용을 가지는 코드를 작성하라고?
 
각 원소를 적어도 한번은 조회해야 할 것 아닌가.
그것만 해도 O(N) 인데, 어떻게 하라는 걸까.
 
 
 
 
이렇게 불편함이 느껴진다면, 한번쯤은 자신이 어떤 관점으로 문제를 바라보고 있는지 점검해볼 필요가 있
다.
자신도 모르게 쓰고 있던 색안경의 정체를 파악하고, 그것을 벗어야 한다.
 
튜닝을 걷어내고, 순정을 볼 필요가 있다.
 
 

---

 
 
 
먼저, 변하지 않는 사실이 있다.
 
우리는 nums의 최솟값 MIN을 원한다는 사실이다.
 
그리고, 이 최솟값을 구하기 위해 N개의 원소를 조회하는 것은 과연 정말 필요한 걸까?
 
 
우리는 흔히 MIN=f(s0,s1, ... s(N-1)) 처럼 생각한다.
즉, 최솟값은 모든 원소에 의존하는 함수라고 자연스럽게 받아들인다.
 
하지만 이 관점은 이미 하나의 색안경이 끼여있다.
문제의 구조를 고려하지 않은채,
데이터를 "전부 읽어야 하는 대상"으로 바라보고 있는 것이다.
 
 
여기서 중요한 사실은 nums은 ascending order를 기반으로 (회전)정렬되어 있다는 사실이다.
즉 원소들은 무질서하게 흩어져 있는 것이 아니라, 서로 강한 구조적 관계를 가지고 있다.
그리고 이는 모든 원소를 직접 보지 않아도 된다는 사실을 가능하게 만든다.
 
 

---

 
 
자. 우리가 쓰고 있었던 색안경의 정체를 파악하였으니
이제 순정을 보자.
 
문제의 구조를 다시 바라보자.
주어진 수열 S=[s0,s1, ... , s(N-1)]은 ascending order를 기반으로 회전된 배열이다.
 
즉, 정확히 하나의 위치 i에서만
si<s(i-1)가 성립하고,
 
그 이외의 모든 위치 i에 대해서는 si>s(i-1)이다.
 
그리고, 그 하나의 si가 최솟값 MIN이다.
즉 우리는 더 이상 MIN=f(s0,s1, ... , s(N-1)) 처럼 모든 원소를 직접 바라볼 필요가 없다.
 
문제는 MIN=si where si<s(i-1) 로 볼 수 있으며, 이는 i의 위치를 찾는 문제로 압축된다.
 

---

 
이제 문제 해결의 실마리를 찾았으니 아이디어를 검증하자.
 
과연 si where si<s(i-1)인 i를 O(logN)에 찾을 수 있는가?
 
가능하다.
 
회전된 ascending order 배열에서는 정렬 구조가 깨지는 지점이 정확히 하나만 존재한다.
따라서 중간 지점을 기준으로 어느 구간이 여전히 정렬 구조를 유지하고 있는지 판단할 수 있고, 이를 통해 최솟값이 존재할 수 없는 절반을 한번에 제거할 수 있다.
 
즉, 매 단계마다 후보 구간을 절반으로 압축할 수 있으므로 전체 시간복잡도는 O(logN) 이다.
 

---

 
찾으려는 i를 g라 하자.
Invariant : g는 구간 [left,right]에 존재한다.
 
mid=(left+right)//2 라 하자.
이때 다음과 같은 두 경우가 가능하다.
1. g가 구간 [left,mid]에 존재하는 경우
2. g가 구간 [mid+1,right]에 존재하는 경우
 
경우 1은 Sright>Smid로 검증할 수 있고, 경우 1의 여집합이 경우 2이므로 else 문으로 완전하게 탐지할 수 있다.
 
 
그리고 이 과정은 left==right가 되는 순간 종료된다.
 
이때 후보 구간의 길이는 1이고, invariant에 의해 g는 여전히 [left,right] 안에 존재한다.
따라서 그 하나의 위치 left가 곧 g이다.
 
 
 

---

 
CODE : Python

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        N=len(nums)
        left,right=0,N-1

        while left<=right:
            if left==right:
                return nums[left]
            mid=(left+right)//2
            if nums[mid]<nums[right]:
                right=mid
            else:
                left=mid+1

 
CODE : Java
 

class Solution {
    public int findMin(int[] nums) {
        int N=nums.length;
        int left=0;
        int right=N-1;

        while (left<=right){
            if (left==right){
                return nums[left];
            }
            int mid=(left+right)/2;
            if (nums[mid]<nums[right]){
                right=mid;
            }
            else{
                left=mid+1;
            }
        }
        throw new IllegalStateException();
    }
}

끝