LeetCode [ 33 | Python ] Search in Rotated Sorted Array
업데이트:
문제
회전 되어 있을지도 모르는 정렬된 배열 nums에서 특정값 target을 찾아내어 그 주소값을 반환해야하는 문제. target이 배열에 존재하지 않는다면 -1을 반환해야 한다.
풀이
시도
실행 시간 : 실패
메모리 : 실패
O(log n)의 빠른 시간으로 해결해야 하는 문제인 점, 배열이 정렬되어 있는 점을 통해 이분탐색을 사용해야 한다고 생각했다.
하지만 관건은 배열이 회전되어 있을지도 모른다는 점인데,
이는 중간 값과 그 오른쪽 값을 비교해 감소하는 구간이 있으면 이를 회전된 배열의 끝과 시작점이라고 판단해 각각 그에 맞게 끔 반대에 해당하는 값을 찾고자 했다.
결과적으로 잘못된 접근법이었다.
우연히 중간 값이 감소 구간이어서 해결할 수도 있지만, 그렇지 않은 경우에는 범위를 잘못 설정해 도출해낸 결과가 산으로가버리게 된다.
각각 포인터들이 가리키는 값들이 다음인 경우가 그 경우겠다.
[7, 8, 0, 3, 5]
m(3) ,l(7), r(5) # m 값을 기준으로하면 l, r 모두 증가한다.
[3, 5, 7, 8, 0] #중간 값 7과 그 오른쪽 값을 비교했을 때 이 배열이 회전되어있는지 여부를 알 수 없다.
class Solution(object):
def search(self, nums, target):
l, r = 0, len(nums) - 1
while l < r:
m = (l + r) // 2
if (nums[m] == target): return m
if nums[m] > nums[m+1] and target < nums[m]: # nums[m] 오른쪽 것 보다 크고 타겟보다 작으면(rotated)
l = m + 1
elif nums[m] > nums[m+1] and target > nums[m]: #nums[m] 이 오른쪽 것 보다 크고 타겟보다 크면(rotated)
r = m
elif nums[m] < nums[m+1] and target < nums[m]:
r = m
elif nums[m] < nums[m+1] and target > nums[m]:
l = m + 1
return -1
해결
이 문제를 해결하기 위해 고려했던 방법은 다음과 같았고, 아래 이유들로 인해 가장 마지막 방법을 택했다.
최대값 또는 최솟값을 기준으로 배열을 잘라붙여 정렬된 배열을 만든다.
-> 메모리를 과다하게 사용하고, 배열을 잘라붙이는 과정에서 이미 시간 복잡도가 O(n) 이상 걸릴 것으로 판단해 시도조차 하지 않았다.가상으로 배열이 왼쪽, 또는 오른쪽으로 더 크게 있다고 가정하고 주소값을 그에 맞게 조작한다.
-> 주소값을 어떻게 조작해야할지 쉽사리 판단이 서지 않았고,-len(nums)-1부터len(nums) * 2를 넘나드는 주소값을 조작하기가 쉽지 않다.- 새로운 기준으로
l,r값을 조작한다.
문제를 해결하면서 알게된 점은 l이 가리키는 값 보다 r이 가리키는 값이 작다면 이는 회전되어 있는 배열이라는 것이다.
이 점에 착안해 다시 접근했다.
- 이분 탐색에 필요한
l과r값을 초기화 한다. - 이분 탐색을 수행한다.
l이 가리키는 값보다m이 가리키는 값이 더 크다면 정상적(통상의 이분탐색대로)으로 비교하며 범위를 축소시킨다.r이 가리키는 값보다m이 가리키는 값이 더 작다면 위 조건의 반대로 범위를 축소시킨다.m이 가리키는 값이target과 같다면 그 주소를 반환한다.
- 이분 탐색이 끝날 때 까지
target과 같은 값을 발견하지 못했다면-1을 반환한다.
class Solution(object):
def search(self, nums, target):
l, r = 0, len(nums) - 1
while l <= r:
m = (l + r) // 2
if nums[m] == target:
return m
if nums[m] >= nums[l]:
if target >= nums[l] and target < nums[m]:
r = m - 1
else:
l = m + 1
elif nums[m] <= nums[r]:
if target > nums[m] and target <= nums[r]:
l = m + 1
else:
r = m - 1
return -1
생각 & 정리
주어진 배열 하나에도 여러개의 힌트를 얻어낼 수 있다는 것을 알았다.
알고있는, 학습한 내용을 그대로 이용하기 보다는 그 핵심 개념을 파악하고 응용해야 한다는 것을 깨닫게 되는 나날인 것 같다.
댓글남기기