[algo/NeetCode] find minimum in rotated sorted array

문제

You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:

• [3,4,5,6,1,2] if it was rotated 4 times.

• [1,2,3,4,5,6] if it was rotated 6 times.

• 배열의 수는 중복 x

• solve : 배열 nums에서 가장 작은 수 찾기

• O(log n) 풀이 필요

문제 링크

---

풀이

막힘1

class Solution {
public:
    int findMin(vector<int> &nums) {
        int st = 0, en = nums.size()-1;
        while (st < en) {
            int mid = (st + en) / 2;
            int st_ = nums[st], en_ = nums[en], mid_ = nums[mid];
            if (st_ > mid_ && en_ > mid_) return mid_;
            else if (st_ < mid_) {
                if (en_ > mid_) en = mid-1;
                else st = mid+1;
            }
        }
        return 0;
    }
};

• 테케 [3,4,5,6,1,2] , [4,5,0,1,2,3]는 통과
• [4,5,6,7] 는 TLE 뜨고 있으며 output으로 0 나옴...

WHY : 왜 틀린 접근인지

• 4,5,6,7 돌려보기
• 2번째에서 st = 2, en = 3, mid = 2 가 나오는데 조건에 분기처리 되어있지 않아 TLI가 뜨고 있음
• 그리고 st, en, mid 가 같을 경우를 대비 안함

HOW : 어떻게 해결하였는지
=을 조건에 추가함

---

막힘2

class Solution {
public:
    int findMin(vector<int> &nums) {
        int st = 0, en = nums.size()-1;
        int mid;

        if (en == 1) {
            int res = nums[0] < nums[1]? nums[0] : nums[1];
            return res;
        }
        while (st <= en) {
            mid = (st + en) / 2;
            int st_ = nums[st], en_ = nums[en], mid_ = nums[mid];
            if (st_ >= mid_) {
                if (en_ >= mid_) return mid_;
            }
            else if (st_ < mid_) {
                if (en_ >= mid_) en = mid-1;
                else st = mid+1;
            }
        }
        return nums[mid];
    }
};

• [2, 1] 에서 output이 2로 출력됨
• 원소 개수가 2개면 int res = nums[0] < nums[1]? nums[0] : nums[1]; 와 같은 꼼수 씀
• [2, 3, 4, 5, 1]에서 막힘 (5가 출력됨)

WHY : 왜 틀린 접근인지

• while (st <= en) 안에서 if (st_ >= mid_) { if (en_ >= mid_) return mid_; } 부분에 else가 없음. en_ < mid_인 경우엔 아무 동작도 안 하고 그냥 다음 반복으로 넘어가버림. → 이 경우에는 갱신x
• 즉 갱신되지 않났는데 while 조건이 참이라서 무한루프
• 조건 처리가 부족

HOW : 어떻게 해결하였는지

• st_, mid_, en_ 세 값을 다 비교하는 방식 대신, mid랑 en(오른쪽 끝)만 비교하는 표준 이분탐색으로 단순화
• 지금 코드처럼 양쪽 끝(st, en)이랑 mid_ 세 개 다 비교해서 분기 나누는 방식은 구간이 짝수로 줄어들어 mid가 st랑 겹치는 경계 상황에서 조건이 꼬이기 쉬움

---

최종 코드

class Solution {
public:
    int findMin(vector<int> &nums) {
        int st = 0, en = nums.size()-1;
        int mid;

        while (st <= en) {
            mid = (st + en) / 2;
            int st_ = nums[st], en_ = nums[en], mid_ = nums[mid];
            if (mid_ > en_) st = mid + 1;
            else if (mid_ < en_) en = mid;
            else return mid_;
        }
        return nums[mid];
    }
};

후기

• 역시 알고리즘은 많은 경우의 수를 느껴보는게 좋은듯... → 즉 많이 문제 풀어야 한다
• 이분탐색은 맨날 st, en, mid 세 값 전부 비교하는 방식만 풀어서 이렇게 중간 mid 와 한쪽 끝 en 만 비교하는 건 처음 풀어봐서 떠올리기 어려웠음
• 고민은 길어도 2일 정도만 하고 ai 이용해서 답 찾고 정리하고 등등 "문제에 대한 경험치"를 많이 쌓는 게 지금 내 실력에서 적당한 학습법인 것 같다.