오늘 문제는 양심상 2번 더 풀었다 ㅎㅎ...

1. 문제

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
약간 문제가 뭔가... 답 도출 부분에 있어서

return the minimum element of this array

라고 하지 않고

return the first element of origin array

라고 했다면... 내가 처음 풀이처럼 풀지는 않지 않았을까 ~ 싶다. ^^

2. 풀이

1. 내 풀이 1: 성공

class Solution:
    def findMin(self, nums: List[int]) -> int:
        return min(nums)

python 내장 함수 가지고 풀기... 깔끔하지만 제일 런타임 시간이 길었다.

2. 내 풀이 2: 성공

class Solution:
    def findMin(self, nums: list[int]) -> int:
        Min = nums.index(min(nums))
        new = [0]*len(nums)
        for i in range(0,len(nums)):
            new[i] = nums[(i+(Min-len(nums)))]
        return new[0]

첫 번째 풀이가 너무 날먹이었던 것 같아... 한 번 도전해보았다. rotated array니까 이걸 다시 orderd array로 바꿔서 첫 번째 element를 반환하자가 목표였다. (인터넷의 다른 풀이도 이게 목표인 것 같았다.)

순서는 다음과 같다.

1. index 내장 함수를 이용해 min(nums)의 위치를 찾았다.
2. 그 후 nums의 길이만큼 0 배열을 만들어준다.
3. 순서대로 쌓아준다.

이때 순서대로 쌓아주는 게 문제라면 문젠데,
마이너스 인덱스를 고려해주면 뭐.. 된다.

배열이 [3, 4, 5, 1, 2]이라고 할 때 1은 index = 3이면서 index = -2이다.
후자의 인덱스의 경우 Min(index 내장 함수를 이용해 구한 1의 위치) - len(nums)를 이용해 구할 수 있다.
그리고 여기서 i를 더해주면 1,2,3,4,5 차례대로 element가 반환된다.

이렇게 한 결과가

이와 같다. 인터넷 풀이보다 빨라서 뿌듯했음.

3. 다른 풀이

해당 코드의 출처는 아래의 블로그이다.
(https://yunmorning.tistory.com/11)

class Solution:
    def findMin(self, nums: list[int]) -> int:
        start = 0
        end = len(nums)-1
        mid = (start+end)//2
        
        if nums[0] <= nums[end]:
            return nums[0]
        
        while mid <= end:
            mid = (start + end)//2
            
            if nums[mid] > nums[mid+1]:
                return nums[mid+1]
            if nums[mid] > nums[0]:
                start = mid +1
            else:
                end = mid
        return nums[0]
            

내 이전 풀이와 비교하기 위해서 한 번 찾아봤다. 대부분 이렇게 풀었던데 사실 이게 무슨 알고리즘인지... 그리고 왜 굳이 이렇게 푸는지는 잘 이해가 안 됐다. 그래도 나름 better 풀이라고 들고와봄...

여튼 이번 주 스터디 문제도 끝!