(Leetcode) 153 - Find Minimum in Rotated Sorted Array

기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.

https://neetcode.io/practice

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

내가 작성한 풀이

생각보다 쉽게 해결되었다.

문제에서는 다음과 같은 예시들을 제공해준다.

• [3,4,5,1,2]
• [4,5,6,7,0,1,2]
• [11,13,15,17]

여기서 rotate 가 되었다면 중간에 숫자가 작아지는 지점이 생긴다. 만약 rotate 가 되지 않았다면 맨 앞자리가 최소의 수이다.

이 규칙을 수식으로 옮기면 된다.

class Solution {
    public int findMin(int[] nums) {
        int p = 0;
        int min = nums[0];
        while(true) {
            if (p == nums.length) {
                break;
            }

            if (nums[p] > nums[p + 1]) {
                min = nums[p + 1];
                break;
            }

            p++;
        }

        return min;
    }
}

TC, SC

시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.

조금 더 최적화 하자면 (binary search like)

문제에서 O(log n) 의 시간복잡도로 풀어보라고 제시하였다. log n 이 들어갔으니 트리같은 방식으로 접근을 하나? 라는 생각이 우선 들었다.

다른 사람들의 풀이를 보니 다음과 푸는 것을 볼 수 있었다.

public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while(left < right) {
        int mid = left + (right - left) / 2;

        if(nums[mid] < nums[right]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return nums[left];
}

case 나눠서 생각해보기

머릿속에서 상상이 잘 가지 않아. 케이스를 나눠서 생각해보았다.

1. [0,1,2,4,5,6,7] 완벽하게 정렬되어 있을 경우

• 첫번째 반복
  • left:0, right: 6 → mid: 3 → right = 3
• 두번째 반복
  • left:0, right: 3 → mid: 1 → right = 1
• 세번째 반복
  • left:0, right: 1 → mid: 0 → right = 0
• 반복 종료
  • return nums[0]

2. [6,7,0,1,2,4,5] 최솟값이 왼쪽에 있을 경우

• 첫번째 반복
  • left:0, right: 6 → mid: 3 → right = 3
• 두번째 반복
  • left:0, right: 3 → mid: 1 → right = 2
• 세번째 반복
  • left:2, right: 3 → mid: 2 → right = 2
• 반복 종료
  • return nums[2]

3. [4,5,6,7,0,1,2] 최솟값이 오른쪽에 있을 경우

• 첫번째 반복
  • left:0, right: 6 → mid: 3 → left = 4
• 두번째 반복
  • left:4, right: 6 → mid: 5 → right = 5
• 세번째 반복
  • left:4, right: 5 → mid: 4 → right = 4
• 반복 종료
  • return nums[4]

4. [1,2,4,5,6,7,0] 최솟값이 오른쪽 맨 끝에 있을 경우

• 첫번째 반복
  • left:0, right: 6 → mid: 3 → left = 4
• 두번째 반복
  • left:4, right: 6 → mid: 5 → left = 6
• 반복 종료
  • return nums[6]

TC, SC

시간 복잡도는 O(log n)이고, 공간 복잡도는 O(1)이다.