자료구조와 알고리즘 -배열(배열 삽입 위치, 병합)

<배열에서 삽입 위치 찾기>

문제) nums = [1,2,3,4,5], target =3 

       target의 위치는?

---

풀이)

'이진탐색'이용 -> 가운데 숫자에 먼저 접근해서 target 값과 비교하고 큰 파트 와 작은 파트로 나누고 해당되는 파트를 찾아간 다음 그 파트이 가운데 숫자와 target값을 비교하면서 위치를 찾아가는 방법

 

(1) 선형순회

def searchInsert(nums: list, target:int) -> int:
    index = 0
    
    while index < len(nums):
        if target <= nums[index]:
            break
            
        index += 1
        
    return index

 

(2) 이진탐색

def BsearchInsert(nums:list, target: int) -> int:
    low =0
    high = len(nums) -1
    
    while low <= high:
        mid = int((low + high)/2)     #mid 값 구하기
        
        if target == nums[mid]:
            return mid
        if target > nums[mid]:       #target값이 mid보다 크면
            low = mid +1            
        else:                              #target값이 mid보다 작으면
            high = mid -1
            
    return low

---

<정렬된 배열의 병합>

 문제) num1, num2 두 배열을 병합(정렬된 상태)

참고자료 : 쓰면서 익히는 알고리즘 구조

---

풀이)

(1) sorted 함수 사용해서 병합하고 정렬(실행이 안됨)

def merge(nums1: list, m: int, nums2:list, n: int) -> None:
    for i, v in enumerate(nums2):
        nums1[m+i] =v
        
    nums1[:] = sorted(nums1)

 

(2) 비교 및 삽입(이해가안됨)

def merge(nums1: list, m:int, nums2: list, n:int) -> None:
    i = m-1
    j = n-1
    k = m+n-1
    
    while i >= 0 and j >= 0:
        if nums1[i] < nums2[j]:
            nums1[k] = nums2[j]
            j -= 1
        else:
            nums1[k] = nums1[i]
            i -=1
            
        k -= 1
        
    while j >= 0:
        nums1[k] = nums2[j]
        k -= 1
        j -= 1