[3부 선형 자료구조] 7장 배열

📌 7) 두 수의 합 ( 리트코드 1. Two Sum )

✔ 풀이 (브루트 포스)

class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

=> 시간 복잡도 O(n2)

✔ 풀이 (in을 이용한 탐색)

class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)-1):
            num = target - nums[i] #i인덱스 다음 인덱스부터 끝까지 나머지 리스트에
            if num in nums[i+1:]:  #더해서 타겟이 되는 값 있는지 확인
                return [i, nums[i+1:].index(num) + (i + 1)]

=> 시간 복잡도 O(n2) , 하지만 in은 파이썬 레벨에서 매번 값을 비교하는 것에 비해 훨씬 더 빨리 실행됨.

✔ 풀이 (첫 번째 수를 뺀 결과 키 조회)

비교나 탐색 대신 한 번에 정답을 찾을 수 있는 방법은? 딕셔너리 사용!
=> 딕셔너리는 해시 테이블로 구현되어 있고, 이 경우 조회는 평균적으로 O(1)에 가능.

class Solution(object):
    def twoSum(self, nums, target):
        nums_dic = {}  #nums_dic = [값 : 인덱스, ...]
        for idx, num in enumerate(nums):
            nums_dic[num] = idx
            
        for idx, num in enumerate(nums):
            if target - num in nums_dic and idx != nums_dic[target - num]:
                return [idx, nums_dic[target - num]]

=>분할 상환 분석에 따른 시간 복잡도는 O(1) 이며, 전체는 O(n)이 된다.

✔ 풀이 (조회 구조 개선)

#초기 내가 생각했던 방법
#class Solution(object):
#    def twoSum(self, nums, target):
#        nums_dic = {}  #nums_dic = [값 : 인덱스, ...]
#        for idx, num in enumerate(nums):
#            nums_dic[num] = idx
#            if target - num in nums_dic and idx != nums_dic[target - num]:
#                return [idx, nums_dic[target - num]]
# = > nums = [3, 3] / target = 6인 case 통과 X


class Solution(object):
    def twoSum(self, nums, target):
        nums_dic = {}  #nums_dic = [값 : 인덱스, ...]
        for idx, num in enumerate(nums):
            if target - num in nums_dic and idx != nums_dic[target - num]:
                return [idx, nums_dic[target - num]]
            nums_dic[num] = idx
#비교후에  nums_dic[num] = idx을 추가해줌으로써, 같은 값을 더해 target이 되는 경우에 
#겹치지 않는 인덱스를 return 할 수 있다.

✔ 풀이 (투 포인터 사용)

class Solution(object):
    def twoSum(self, nums, target):
        #각 두개의 포인터의 합이 target보다 작으면 왼쪽포인터를 오른쪽으로 이동,
        #target보다 크면 오른쪽 포인터를 왼쪽으로 이동
        #단, nums가 정렬되어 있어야함
        nums.sort()  #정렬 => 인덱스 값 섞임
        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left] + nums[right] < target:
                left += 1
            elif nums[left] + nums[right] > target:
                right -= 1
            else:
                return [nums[left], nums[right]]
        
        #해당 문제에선 인덱스를 반환해야 하기 때문에 다음과 같은 방식으로 풀면 안됨
        #값을 반환하는 문제이면 다음과 같은 방법을 사용할 수 있음

=> 시간 복잡도 O(n)

📌 8) 빗물 트래핑 ( 리트코드 42. Trapping Rain Water )

✔ 풀이 (투 포인터 사용)

#최대 높이는 부피에 영향 주지 X
#그저 왼쪽과 오른쪽 가르는 역할!

class Solution(object):
    def trap(self, height):
        
        if not height:  #[]인 경우
            return 0
        
        volume = 0
        left, right = 0, len(height) - 1
        max_left, max_right = height[left], height[right]
        
        while left < right: 
            max_left = max(max_left, height[left])
            max_right = max(max_right, height[right])
            
            #더 높은 쪽을 향해 투 포인트 이동 
            #=> 높이가 최대인 지점에서 투 포인트 만남
            if max_left <= max_right:
                volume += max_left - height[left]
                left += 1
            else:
                volume += max_right - height[right]
                right -= 1
        
        return volume

=> 시간 복잡도 O(n)

✔ 풀이 (스택 쌓기)

#최소 3개의 구간이 존재해야 물이 고일 수 있는 환경이 만들어짐
#현재 높이가 이전 높이보다 클 경우
#3개의 구간을 잡고, 해당구간으로 만들어 지는 물의 부피를 더해준다
#-> top = stack.pop() 하면 3개의 구간의 인덱스는 stack[-1], top, i(현재)
#-> 물의 부피는 가로*세로

class Solution(object):
    def trap(self, height):
        volume, stack = 0, []
        for i in range(len(height)):
            #stack에 있는 인덱스들의 높이가 현재의 높이보다 작을 경우 계속 반복
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop() #중간 구간
                
                #stack이 비어있는 경우(=3개의 구간을 만들 수 없는 경우) 빠져나감
                if not stack:
                    break
                    
                #처음 구간 stack[-1] / 중간구간 top / 마지막구간 i
                width = i - stack[-1] - 1 #가로
                length = min(height[i], height[stack[-1]]) - height[top] #높이
                
                volume += width * length
                
            stack.append(i)

        return volume
            

=> 시간 복잡도 O(n)

📌 9) 세 수의 합 ( 리트코드 15. 3Sum )

✔ 풀이 (부르트 포스)

class Solution(object):
    def threeSum(self, nums):
        
        result = []
        nums.sort()  #중복제거를 간소화 시키기 위해 정렬
        for i in range(len(nums) - 2):
            #중복인 경우 건너띄고 다음으로 넘어감
            if i > 0 and nums[i] == nums[i - 1]:
                continue
                
            for j in range(i + 1, len(nums) - 1):
                #중복인 경우 건너띄고 다음으로 넘어감
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                    
                for k in range(j + 1, len(nums)):
                    #중복인 경우 건너띄고 다음으로 넘어감
                    if k > j + 1 and nums[k] == nums[k - 1]:
                        continue
                        
                    #세 개의 수 합
                    if nums[i] + nums[j] + nums[k] == 0:
                        result.append([nums[i], nums[j], nums[k]])
        
        return result

=> 시간초과
=> 시간 복잡도 O(n3)

✔ 풀이 (투 포인터)

class Solution(object):
    def threeSum(self, nums):
        
        result = []
        nums.sort()   #중복제거 간소화 하기 위해 정렬
        
        for i in range(len(nums)-2):
            #중복 일 경우 건너 뜀
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            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:
                    result.append([nums[i], nums[left], nums[right]])
                    
                    #정답에 중복이 들어가면 X => 중복처리
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    
                    #정답일 경우 투 포인터 이동
                    left += 1
                    right -= 1
                    
        return result

=> 시간 복잡도 O(n2)

📌 10) 배열 파티션1 ( 리트코드 561. Array Partition 1)

✔ 풀이 (오름차순 풀이)

class Solution(object):
    def arrayPairSum(self, nums):
        pair, sum = [], 0
        nums.sort()
        
        for num in nums:
            pair.append(num)
            
            if len(pair) == 2:
                sum += min(pair)
                pair = []
        
        return sum

=> 시간 복잡도 O(n)

✔ 풀이 (짝수 번째 값 계산)

class Solution(object):
    def arrayPairSum(self, nums):
        
        nums.sort()
        
        sum = 0
        for idx, num in enumerate(nums):
            
            if idx % 2 == 0:  #짝수 인덱스일 경우
                sum += num
        
        return sum

=> 시간 복잡도 O(n)

✔ 풀이 (파이썬 다운 방식)

class Solution(object):
    def arrayPairSum(self, nums):
        return sum(sorted(nums)[::2])

=> 시간 복잡도 O(n)

📌 11) 자신을 제외한 배열의 곱 ( 리트코드 238. Product of Array Except Self )

• 해당 문제를 보자마자 생각나는 풀이는 전체를 곱한 수에 각 인덱스에 존재하는 값들로 나누어 해당 인덱스에 덮어씌우는 풀이이다.
  => 나눗셈을 하지 않고 O(n)에 풀이하는 방법은?

✔ 풀이

class Solution(object):
    def productExceptSelf(self, nums):
        #out = 현재위치 i를 제외한 배열의 곱
        out = []
        
        #현재위치 i를 제외한 왼쪽 배열의 곱
        p = 1
        for i in range(len(nums)):
            out.append(p)
            p *= nums[i]
        
        #i를 제외한 오른쪽 배열의 곱을 out에 곱해줌
        p = 1
        for i in range(len(nums) - 1, -1, -1):
            out[i] *= p
            p *= nums[i]
        
        return out

=> 시간 복잡도 O(n)

📌 12) 주식을 사고팔기 가장 좋은 시점 ( 리트코드 121. Best Time to Buy and Sell Stock )

부르트 포스 말고 다른 풀이는?

✔ 풀이

# 최소 초기값 => sys.maxsize / float('inf')
# 최대 초기값 => -sys.maxsize / float('-inf')
class Solution(object):
    def maxProfit(self, prices):
        
        profit, min_price = 0, sys.maxsize
        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)

        return profit

=> 시간 복잡도 O(n)