×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,101,745명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :

 

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

 

Search Insert Position - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

 

알고리즘 분석 :


문제 해결에 필요한 사항

1. Binary search

 

이분탐색을 통해 해결 할 수 있다.

 

target이 위치할 수 있는 최소 위치를 찾아야하는 것이고 이분탐색을 통해 어느 인덱스에 위치해야할 지 결정할 수 있다.

이때 사실 이분탐색이 아닌 linear search로도 해결이 가능하다.

 

 

 
class Solution(object):
    def searchInsert(self, nums, target):
        left = 0
        right = len(nums) - 1
        ans = 0
        if target <= nums[0]:
            ans = 0
        elif target > nums[-1]:
            ans = len(nums)
        else:
            while left <= right:
                mid = (left + right) // 2

                if nums[mid] == target:
                    ans = mid
                    break
                if target < nums[mid]:
                    right = mid - 1
                else:
                    ans = left = mid + 1

        return ans

 

 

소스 코드 : 

 

//                                                       This source code Copyright belongs to Crocus

//                                                        If you want to see more? click here >>

반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[2636번] 치즈  (1) 2021.06.01
[11번] Container With Most Water  (0) 2021.05.10
[35번] Search Insert Position  (0) 2021.05.07
[1018번] 체스판 다시 칠하기  (0) 2020.03.16
[17472번] 다리 만들기 2  (0) 2020.03.14
[SwExpertAcademy] 아나그램  (0) 2020.01.04