4 분 소요

Binary Search

문제

문제 링크

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

Example 3:

Input: nums = [1], target = 0 Output: -1

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -104 <= target <= 104

스스로 고민

접근법

  • 문제에서 배열이 정렬되어 있기는 하지만 random으로 rotations 되어있다.
    • [1,2,3,4,5] -> [3,4,5,1,2]
  • index를 뽑아서 문제를 풀 수도 있지만 sort() 함수를 사용할 경우 0(nlog n) 이 되어버리기 때문에 배열의 크기가 클 경우 통과를 못 할 수 가 있다.
  • 이진 탐색으로왼쪽과 오른쪽을 정렬하면서 진행해야한다.

의사코드

  • 왼쪽과 오른쪽의 인덱스를 만들어준다. 왼쪽은 0 오른쪽은 len 함수를 사용해서 인덱스를 만들어준다. nums 가 [1,2,3,4] 이렇게 있을 경우 len(nums) 값은 4 그렇기 때문에 -1 을 해줘서 마지막 숫자 4의 인덱스 3이 최종 값으로 나올 수 있게 만들어준다.
  • while 문을 통해 해당 인덱스에 도달할 때까지 작업을 수행한다.
  • mid 는 (right + left) //2 로 할 경우 합이 홀수가 나와도 몫만 가져갈수 있고 짝수일 경우 자동으로 소수점이 남는데 그렇게 되지 않도록 해결이 가능하다.
  • 만약 중간 값의 index의 nums 값이 target 값과 같을 경우 mid를 바로 반환
  • 가장 왼쪽이 중간 값과 같거나 작을 때
    • 타겟 값이 가장 왼쪽의 값과 중간 값 사이에 있을 때
      • right의 값의 인덱스를 -1 를해서 해당 조건에서 답이 나올 때 까지 탐색
      • 그렇지 않을 경우 왼쪽을 + 1로 해서 다음 while문에서 바로 else 구문으로 가도록 만든다.
    • 위의 조건이 맞지 않게 되는 경우는 left 값이 mid 값의 +1이 되는 경우다.
      • 똑같은 논리로 target 값이 mid + 1 과 가장 오른쪽 값에 있을경우
        • left는 현재 mid에서 +1 상태이니 거기서 또 오른쪽으로 하나 이동
        • 그렇지 않을 경우 지금 현재 nums 안에 target 값이 없는 상황이니 while 문을 종료하기 위해 right = mid -1 을 해준다. 이렇게 될 경우 left = mid +1 이고 right 는 mid - 1 이니 while 문의 left <= right는 false가 되고 return -1이 실행되도록 만든다.

구현 코드

class Solution:

    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:

            mid = right + left // 2

            if nums[mid] == target:

                return mid

            if nums[left] <= nums[mid]:

                # 왼쪽 정렬

                if nums[left] <= target < nums[mid]:

                    right = mid - 1

                else:

                    left = mid + 1

            else:

                # 오른쪽 정렬

                if nums[mid] < target <= nums[right]:

                    left = mid + 1

                else:

                    right = mid - 1

        return -1

시간 복잡도와 공간 복잡도

  • 시간복잡도: 이진 검색 알고리즘을 사용하므로 시간복잡도는 O(log n)다. 배열의 크기에 상관없이 빠르게 타겟을 찾을 수 있다.

  • 공간복잡도: 주어진 입력 배열 nums를 제외하면 상수 공간만을 사용하므로 공간복잡도는 O(1)다. 추가 메모리를 사용하지 않고 문제를 해결할 수 있다.

회고 과정

  • rotation 개념 하나 들어갔는데 이 부분이 헷갈려서 시간이 정말 오래걸렸다.
  • 무지성으로 작성하면 if문이 계속 늘어나서 어떻게 하면 while 문 하나로 끝낼 수 있는지에 대해 고민을 정말 많이 했던 것 같다.
  • 알고리즘을 풀수록 나에 대해 스스로 평가하자면 문제를 보자마자 해결을 팍팍 할 수 있는 능력이 매우 부족하다고 생각했다.
  • 그마나 이전에 이진탐색 패턴으로 푼 경험이 있어서 그걸 응용해서 풀었는데 이마저도 오래걸린걸 보면 실력이 늘기 전까지는 최대한 패턴을 많이 공부하고 익히는 게 지금은 배스트인 것 같다.
  • 알고리즘 부분에 재능이 있는 것 같지는 않은데 그렇다고 포기할 수는 없으니 문제를 보자마자 바로 해결할 수 있는 자신감이 생기기 전까지는 최대한 많은 문제를 풀어보면서 패턴들을 익혀야 될 것 같다.

    다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for x,y in enumerate(nums):
            if(y == target):
                return x
        return -1

  • 시간복잡도: 주어진 배열 nums를 순회하면서 각 요소를 target과 비교하는 작업을 수행한다. 따라서 최악의 경우에는 배열의 모든 요소를 순회해야 하므로 시간복잡도는 O(n) 다. 여기서 n은 배열 nums의 길이다.

  • 공간복잡도: 주어진 입력 배열 nums와 몇 가지 변수(예: x, y)만 사용하므로 공간복잡도는 O(1) 다. 추가적인 메모리를 사용하지 않고 문제를 해결할 수 있다.

느낀점

  • 수업시간에 배운 해시맵을 통해 문제를 해결한 케이스다.
  • nums를 해시맵으로 풀어버린 뒤에 벨류 값이 target 값과 가타면 거기에 맞는 인덱스 x 를 반환하고 그런 값이 없다면 -1로 리턴하는 함수다.
  • 이진탐색으로도 찾을 수 있었지만 솔직히 해시맵으로 문제를 풀 수 있다는 생각 자체를 떠올리지 못 한 걸 보면 아직 해시맵도 제대로 이해를 못 한것 같다.
  • 이진탐색이든 해시맵이든 문제를 보고 자신있게 적용할 수 있을 때까지 연습해야 될 것 같다.

댓글남기기

참고