[알고리즘 / 초급] Binary Search Insert

[알고리즘 / 초급] Binary Search Insert

반응형

Leetcode의 다음 문제에 대한 풀이입니다

https://leetcode.com/problems/search-insert-position/

문제

정렬된 배열과, 목표값을 가지고 만약 목표값이 배열안에 있으면 그 인덱스를 return하고, 없다면 target값이 들어가기 적합한 위치의 인덱스를 return

예시

Input: nums = [1,3,5,6], target = 5 Output: 2

Input: nums = [1,3,5,6], target = 2 Output: 1

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

Input: nums = [1,3,5,6], target = 0 Output: 0

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

조건

Time Complexity : O(log n)

1 <= nums.length <= 104

-104 <= nums[i] <= 104

<= nums[i] <= 104 nums는 각기 고유한 값을 가지며, 오름차순 정렬 되어있음

-104 <= target <= 104

풀이

O(log n)를 만족시키려면 Binary Search를 이용해야 합니다. Memory를 아끼려면 Array(List)를 계속해서 다시 만들지 말고, index값을 이용해서 메모리를 아끼도록 합시다

public int searchHelper(int start, int end, int target, int[] nums){ //베이스 케이스 1. start와 end 인덱스가 같다면 멈춤 //케이스 2. nums[start] 값이 target과 같다면, start return //케이스 3. nums[end] 값이 target과 같다면, end return //케이스 4. nums[(start+end)/2] 값이(중앙값) target과 같다면, (start+end)/2 return //여기선 recursion // nums[(start+end)/2]> target 이면 중간기준 왼쪽에서 search // nums[(start+end)/2]< target 이면 중간기준 오른쪽에서 search //모든 경우에 맞지 않다면 0 }

위의 Helper 기능을 이용합니다.

여기서 자바의 속성을 이용할 수 있습니다. 자바의 int의 경우 2.xxyy로 계산되는 값은 2로 계산됩니다.

예를 들어 int 3/2 -> 1.5 -> 1로 반환 됩니다.

답은 여기에

더보기 class Solution { public int searchInsert(int[] nums, int target) { return searchHelper(0, nums.length-1, target,nums); } public int searchHelper(int start, int end, int target, int[] nums){ if(start==end){ if(nums[start]target){ return searchHelper(start,(start+end)/2, target, nums); } if(nums[(start+end)/2]

저보다 잘하시는 분도 있겠지만, 위의 코드로 했을때 성적은 다음과 같습니다.

메모리사용

약 상위 55% 정도의 메모리 사용이라고 보면 될 것 같습니다.

반응형

from http://dfso2222.tistory.com/205 by ccl(A) rewrite - 2021-12-10 21:01:59