문제는 여기에서 볼 수 있다.
문제 설명
문제를 간략하게 설명하자면,
입력으로 들어오는 숫자 배열과 하나의 target 숫자가 있고
target 숫자가 배열 안에 존재하면 해당 target이 위치한 인덱스를,
존재하지 않으면 -1을 return 하는 문제이다.
단, 입력되는 숫자 배열에 몇 가지 조건이 있는데
1. 배열 안의 모든 숫자는 중복되지 않는다.
2. 배열 안의 모든 숫자는 오름차순이지만, 아래 3번의 규칙을 따른다.
3. 배열 안의 숫자들은 특정 숫자(pivot)를 기준으로 rotate 되었다.
예를 들면, [0, 1, 2, 3]이라는 배열은 0이라는 숫자를 기준으로 [2, 3, 0, 1]처럼 rotate 될 수 있고,
1이라는 숫자를 기준으로 [1, 2, 3, 0]처럼 rotate 될 수 있다.
풀이 1
사실 파이썬의 "in"과 ".index"를 사용하면 아래와 같이 단 네 줄로 코딩이 가능하다.
class Solution:
def search(self, nums: List[int], target: int) -> int:
if target in nums:
return nums.index(target)
else:
return -1
그런데 위 풀이는 아래처럼 성능이 조금 안좋다.
그래서 나는 위의 코드를 좀 더 풀어 작성해보려고 했다.
풀이 2
결론적으로 내가 생각해내어 풀어낸 알고리즘은 Two-Pointer 였다.
사실 알고리즘 코딩 문제에서 투 포인터는 너무나 자주 사용되어서
가장 먼저 적용해보게 된다.
코드를 먼저 보자.
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left < right:
while nums[left] < target and target > nums[right] and left < right:
left += 1
while nums[left] > target and target < nums[right] and left < right:
right -= 1
if nums[left] == target:
return left
if nums[right] == target:
return right
if nums[left] < target and target < nums[right]:
left += 1
right -= 1
else:
return -1
if nums[left] == target:
return left
return -1
난 nums 배열의 left나 right 위치에 존재하는 숫자가 target인 경우를 제외하고,
네 가지의 경우의 수를 생각했다.
while 문 안에 존재하는 두 개의 while 문과 하단의 if-else 문이 그것인데,
nums라는 숫자 배열을 순회하다 보면 결국 저 네 가지의 경우만 존재한다는 것을 알 수 있다.
위와 같은 풀이의 성능은 아래와 같다.
굉장히 빠르다!
끝!
