[Python] Array (2)

In [1]:

from typing import List, Set, Dict, Tuple

 

Problem 9. 3Sum

https://leetcode.com/problems/3sum/

---

실행시간 비교

 

풀이	방식	Big-O	실행시간 순위
1	브루트 포스로 계산	O(n³)	2위
2	Two Pointer	O(n²)	1위

---

Solution 1. 브루트 포스로 계산

 

In [8]:

def three_sum_1(nums: List[int]) -> List[List[int]]:
    results = []
    nums.sort()
    
    # 브루트 포스 3회 반복
    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:
                    results.append([nums[i], nums[j], nums[k]])
    return results

 

In [9]:

three_sum_1([-1,0,1,2,-1,-4])

 

Out[9]:

[[-1, -1, 2], [-1, 0, 1]]

 

---

Solution 2. Two Pointer

 

In [13]:

def three_sum_2(nums: List[int]) -> List[List[int]]:
    results = []
    nums.sort()
    
    # 브루트 포스 3회 반복
    for i in range(len(nums)-2):
        # 중복된 값 건너뛰기
        if i > 0 and nums[i] == nums[i-1]:
            continue
        
        # two pointer로 간격 좁혀가며 계산
        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으로 조건 만족하므로 정답 처리
                results.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
                
                # 이동하면서 다음 턴으로 넘어가기
                left += 1
                right -= 1
                
    return results

 

In [14]:

three_sum_2([-1,0,1,2,-1,-4])

 

Out[14]:

[[-1, -1, 2], [-1, 0, 1]]

 

---

Problem 10. Array Partition 1

https://leetcode.com/problems/array-partition-i/

---

실행시간 비교

 

풀이	방식	Big-O	실행시간 순위
1	오름차순 풀이	O(n)	3위
2	짝수번째 값만 계산	O(n)	2위
3	Pythonic way : slicing and sum	O(n)	1위

---

Solution 1. 오름차순 풀이

 

In [103]:

def array_pair_sum_1(nums: List[int]) -> int:
    sum = 0
    pair = []
    nums.sort()
    
    for n in nums:
        # 앞에서부터 오름차순으로 두 개의 원소를 페어로 만들어 합 산출
        pair.append(n)
        if len(pair) == 2: # pair안에 원소가 2개만 들어선 순간
            sum += min(pair) # pair안의 합을 sum에 더해주기
            pair.clear() # pair 초기화
    return sum

 

In [104]:

array_pair_sum_1([1,4,3,2])

 

Out[104]:

4

 

---

Solution 2. 짝수번째 값만 계산

 

In [106]:

def array_pair_sum_2(nums: List[int]) -> int:
    sum = 0
    nums.sort()
    
    for i,n in enumerate(nums):
        # 짝수 번째 값의 합 계산
        if i % 2 == 0:
            sum += n
    return sum

 

In [107]:

array_pair_sum_2([1,4,3,2])

 

Out[107]:

4

 

---

Solution 3. Pythonic way : slicing and sum

 

In [108]:

def array_pair_sum_3(nums: List[int]) -> int:
    return sum(sorted(nums)[::2])

 

In [109]:

array_pair_sum_3([1,4,3,2])

 

Out[109]:

4

 

---

Problem 11. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/

---

실행시간 비교

 

풀이	방식	Big-O	실행시간 순위
1	교재 : 변수를 변화시키는 방법	O(n)	비슷
2	내 풀이 : slicing과 eval을 이용	O(n)	비슷

---

Solution 1 교재 풀이 방식 : 변수를 변화시키는 방법

 

In [111]:

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

 

In [136]:

product_except_self_1([1,2,3,4])

 

Out[136]:

[24, 12, 8, 6]

 

---

Solution 2 내 풀이 방식 : slicing과 eval을 활용

 

In [29]:

# 첫번째 시도 : 가다듬어 지지 않아 left, right의 초깃값이 매끄럽지 않음
def product_except_self_2(nums: List[int]) -> List[int]:
    nums = list(map(str, nums)) # eval을 활용하기 위해 nums의 원소 타입 변경
    left, right = [['1']], [] # left는 ['1']로 시작하므로 미리 값을 할당하고 시작

    for i in range(1,len(nums)): # 자기 자신을 제외한 양쪽 부분을 리스트로 생성하여
        left.append(nums[0:i]) # 왼쪽 파트는 left에 리스트 형태로 원소를 추가하고
        right.append(nums[i:]) # 오른쪽 파트는 right에 리스트 형태로 원소를 추가함
    right.append(['1']) # right는 ['1']로 끝나므로 마지막에 원소 추가
    
    print(f'left : {left}')
    print(f'right : {right}')
    
    # left와 right의 값을 순서대로 서로 곱하여 ans에 추가
    ans = [eval('*'.join(l)) * eval('*'.join(r)) for l,r in zip(left, right)]
    
    return ans

 

In [30]:

# 생성된 중간 산출물 left, right와 답안 확인
product_except_self_2([1,2,3,4])

 

left : [['1'], ['1'], ['1', '2'], ['1', '2', '3']]
right : [['2', '3', '4'], ['3', '4'], ['4'], ['1']]

 

Out[30]:

[24, 12, 8, 6]

 

In [31]:

# 조금 더 가다듬어진 형태의 풀이
# 결과와 방식은 위와 같지만, left와 right 자체가 숫자로 구성되며
# ['1']을 따로 추가해줬던 설정 두 번이 제거되었다.

def product_except_self_3(nums: List[int]) -> List[int]:
    nums = list(map(str, nums))
    left, right = [1]*len(nums), [1]*len(nums)

    for i in range(1,len(nums)):
        left[i] *= eval('*'.join(nums[0:i]))
        right[i-1] *= eval('*'.join(nums[i:]))

    print(f'left : {left}')
    print(f'right : {right}')
    
    ans = [l*r for l,r in zip(left,right)]
    
    return ans

 

In [32]:

# 순서대로 left, right, ans 결과값 확인
product_except_self_3([1,2,3,4])

 

left : [1, 1, 2, 6]
right : [24, 12, 4, 1]

 

Out[32]:

[24, 12, 8, 6]

 

---

Problem 12. Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

---

실행시간 비교

 

풀이	방식	Big-O	실행시간 순위
1	브루트 포스	O(n)	2위
2	저점을 기준으로 한 차이 계산	O(n)	1위

---

Solution 1. 브루트 포스

 

In [21]:

def max_profit_1(prices: List[int]) -> int:
    # 최대 이득 초깃값 설정
    max_price = 0
    
    for i, price in enumerate(prices): # 구입 시점
        for j in range(i, len(prices)): # 판매 시점
            max_price = max(prices[j] - price, max_price) # max(현재 이득, 기록된 최고 이득)
    return max_price

 

In [22]:

max_profit_1([7,1,5,3,6,4])

 

Out[22]:

5

 

---

Solution 2. 저점을 기준으로 한 차이 계산

최저점과 최대 이득 두가지를 모두 계속 갱신해나가는 방식

 

In [25]:

import sys

def max_profit_2(prices: List[int]) -> int:
    profit = 0
    min_price = sys.maxsize
    
    # 최솟값과 최댓값을 계속 갱신
    for price in prices: # 현재 가격
        min_price = min(min_price, price) # 최저점 갱신
        profit = max(profit, price - min_price) # 최대 이득 갱신
    return profit

 

In [26]:

max_profit_2([7,1,5,3,6,4])

 

Out[26]:

5

 

출처 : 파이썬알고리즘인터뷰