[알고리즘] 6번째 알고리즘 문제 풀기

[SongGwanSeok]

📝 Description

무엇을?

• https://leetcode.com/problems/filling-bookcase-shelves/description/
• https://leetcode.com/problems/search-in-rotated-sorted-array/description/

왜?

• (ex 사용자를 인증하기 위해)

[SongGwanSeok]

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

    int nextIdx(int cur, int maxSize){
        if(cur + 1 > maxSize){
            return 0;
        }
        return cur + 1;
    }

    int prevIdx(int cur, int maxSize){
        if(cur == 0){
            return maxSize;
        }
        return cur - 1;
    }

    int search(vector<int>& nums, int target) {
        int maxIdx = nums.size() - 1;
        int cur = 0, recur = 0;

        if(maxIdx == 0){
            if(nums[0] == target){
                return 0;
            }else{
                return -1;
            }
        }

        while(recur < maxIdx * 2){
            if(nums[cur] == target){
                return cur;
            }else if(nums[cur] < target){
                cur = nextIdx(cur, maxIdx);
                if(nums[cur] > target){
                    return -1;
                }
            }else if(nums[cur] > target){
                cur = prevIdx(cur, maxIdx);
                if(nums[cur] < target){
                    return -1;
                }
            }
            recur++;
        }
        return -1;
    }