7장_ 배열 요약 정리

배열 : 메모리 공간 기반의 연속 방식의 기본 자료형으로 , 고정된 크기만큼의 연속된 메모리 할당이다. 

 

두 수의 합 : 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하는 문제 

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i, n in enumerate(nums):
        complement = target-n

        if complement in nums[i+1:]:
            return [nums.index(n),nums[i+1:].index(complement)+(i+1)]

in을 이용한 탐색 :  in의 시간 복잡도 O(n)이고 전체 시간 복잡도는 O(n^2)

 

비교나 탐색 대신에 한 번에 정답을 찾을 수 있는 방법 

 

def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_map={}
    # 키와 값을 바꿔서 딕셔너리에 저장
    for i,num in enumerate(nums):
        nums_map[num] = i
    # 타겟에서 첫 번째 수를 뺀 결과를 조회
    for i,num in enumerate(nums):
        if target-num in nums_map and i != nums_map[target-num]:
            return [i,nums_map[target-num]]

첫 번째 수를 뺀 결과 키 조회 : 시간복잡도 평균적으로 O(1)에 가능하다.  최악일 경우만 O(n)

 

빗물 트래핑 : 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하는 문제 

 

def trap(self, height: List[int])-> int:
    if not height:
        return 0
    volume = 0
    left,right=0, len(height)-1
    left_max,right_max = height[left],height[right]

    while left<right:
        left_max,right_max = max(height[left],left_max),max(height[right],right_max)
        #더 높은 쪽을 향해 투 포인터 이동
        if left_max <= right_max:
            volume += left_max - height[left]
            left+=1
        else:
            volume += right_max - height[right]
            right+=1
        return volume

투 포인터를 최대로 이동하여 푼것 O(n)에 풀이가 가능 

 

def trap(self, height: List[int])-> int:
    stack=[]
    volume = 0

    for i in range(len(height)):
        # 변곡점을 만나는 경우
        while stack and height[i] > height[stack[-1]]:
            #스택에서 꺼낸다.
            top = stack.pop()
            
            if not len(stack):
                break
            # 이전과의 차이만큼 물 높이 처리
            distance = i - stack[-1]-1
            waters = min(height[i],height[stack[-1]])-height[top]

            volume += distance * waters

        stack.append(i)
    return volume

스택 쌓기를 이용하여 푼것, 마찬가지로 O(n)

 

세수의 합 : 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라

 

def threeSum(self, nums: List[int])-> List[List[int]]:
    results=[]
    nums.sort()

    for i in range(len(nums)-2):
        #중복된 값 건너뛰기
        if i >0 and nums[i] ==nums[i-1]:
            continue
        #간격을 좁혀가며 합 sum 계산 
        left, right = i+1,len(nums)-1
        while left< right:
            sum = nums[i] + nums[left] + nums[right]
            if sum<0:
                left+=1
            elif sum>0:
                right+=1
            else:
                # sum = 0인 경우이므로 정답 및 스킵 처리 
                result.append([nums[i],nums[left],nums[right]])

                while left< right and nums[left] == nums[left+1]:
                    left+=1
                while left< right and nums[right] == nums[right-1]:
                    right-=1
    return results

 

투 포인터로 합 계산

 

투포인터:  시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제풀이 전략으로

배열이 정렬되어 있을 때 유용함 (sort)

 

자신을 제외한 배열의 곱 : 배열을 입력받아 output [i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라

 

def productExceptSelf(self, nums: List[int])->List[int]:
    out = []
    p = 1
    #왼쪽 곱셈
    for i in range(0,len(nums)):
        out.append(p)
        p = p*nums[i]
    p = 1
    #왼쪽곱셈결과에 오른쪽 값을 차례대로 곱셈
    for i in range(len(nums)-1,0-1,-1):
        out[i] = out[i]*p 
        p=p*nums[i]
    return out