99클럽(2기) - 코테스터디 13일차 TIL # Binary Search

LeetCode - 35. Search In Position 

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

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

• Constraints
  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums contains distinct values sorted in ascending order.
  • -104 <= target <= 104

---

 

1. 첫 번째 풀이

 원래는 풀이 과정을 머릿속으로 그려보고 답을 낼 수 있을 것 같다는 생각이 들 때 코드를 치기 시작하는데 오늘은 확신이 안 서서 일단 문제를 풀기 시작했다. 역시나.. 특정 지점에서 손을 못 대고 1시간이 흘러서 채찍피티의 도움을 받았다. 일단 아래와 같이 풀어보려고 했다.

 

1) nums 안에 target이 있으면 target의 인덱스 바로 반환

  O(log n)의 시간복잡도 안에 문제를 풀어야 한다는 조건이 있었는데 이 부분부터 O(n)의 시간복잡도가 소요되어 Recurssion 에러가 발생했다. 

 

2) nums의 원소 개수가 1이 되기 전까지 재귀적으로 이분 탐색

 

3) nums의 원소의 개수라 1일 때 해당 원소와 target의 값을 비교....하려고 하였으나!

     nums의 원소가 하나밖에 안 남았기 때문에 인덱스는 무조건 0일 것이다. 이런,,😓 이 이후의 해결책이 생각나지 않았다.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        elif len(nums) > 1:
            # 위치를 어떻게 효율적으로 찾을 것인가? -> 이진 탐색
            mid = len(nums) // 2
            if nums[mid] < target:
                return self.searchInsert(nums[mid:], target)
            else:
                return self.searchInsert(nums[:mid], target)
        else:
            # 원소가 하나밖에 안 남았는데 인덱스를 어떻게 찾지????? ㅠㅡㅠ

 

 

2. 두 번째 풀이

 채찍피티의 답을 보고 아..! 영감을 얻은 후 안 보고 다시 한번 풀어보았다. 

 

1) left와 right에 nums의 양 끝 인덱스를 할당

  두 개의 포인터를 양 끝에 두고 점점 좁혀가는 형상으로 이분탐색을 진행할 것이므로.

 

2) left가 right보다 커지기 전까지 while문 안에서 이분탐색

  중간값, 왼쪽과 오른쪽 투 포인터를 가지고 target을 찾는 범위를 반씩 없애나간다. 중간값의 인덱스는 left와 right를 더한 값을 2로 나눈 몫이고, target이 중간값에 해당하면 바로 중간값의 인덱스를 반환해준다. 만약 중간값이 target보다 작다면 중간값 이하의 값들은 볼 필요가 없으니 left 포인터에 중간값 인덱스보다 1 큰 값을 할당한다. 중간값이 target보다 크다면 중간값 이상의 값들은 고려 대상에서 제외하면 되므로 right 포인터에 중간값 인덱스보다 1 작은 값을 할당한다. 

 

3) left가 right보다 커지면 left값 반환

 left 값이 right 값보다 커지면 while문을 빠져나오게 되며, 이 값이 nums 안에 target이 없는 경우 target이 들어갔을 때의 인덱스가 된다. 왜냐하면 left가 항상 target이 들어갈 수 있는 최소 인덱스이기 때문이다!

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1 # left와 right에 양 끝의 인덱스를 할당
        while left <= right:
            mid = (left + right) // 2 # 중간값의 인덱스는 left와 right를 더한 값을 2로 나눈 몫
            if nums[mid] == target: # 중간값과 target이 같으면 바로 해당 중간값의 인덱스 반환
                return mid
            elif nums[mid] < target: # 중간값이 타겟보다 작으면 중간값보다 작은 값들은 고려 대상에서 제외
                left = mid + 1
            else:
                right = mid - 1 # 중간값이 타겟보다 크면 중간값보다 큰 값들은 고려 대상에서 제외
        
        return left # left가 right보다 커져서 while문을 빠져나오면 반환

 

 

3. 느낀점

 오늘 처음 문제를 보고 오 쉽게 풀리겠는데? 라고 생각했지만 장장 1시간 반을 붙잡고 있었다. 풀이가 떠오르지 않아서 너무 답답했다.. 시간 제한을 두고 풀어서 비효율적으로 쓰는 시간을 최대한 줄여야겠다. 지금 단계에서는 문제를 집요하게 해결하는 것도 중요하지만 많은 문제들을 접해보는 것이 더 중요한 것 같다.