[Book Review] Python Algorithm Interview (4)

[Book Review] Python Algorithm Interview (4) : 배열

1. 배열

배열

• 값 or 변수 엘리먼트의 집합으로 구성된 구조
• 하나 이상의 인덱스 또는 키로 식별됨

자료구조 분류
1) 메모리 공간 기반의 연속 방식 (배열)
2) 포인터 기반 연결 방식

ADT(abstract data type) 추상자료형
실제 구현 대부분은 배열 또는 연결리스트를 기반으로 한다.
(ex. 스택 : 연결리스트 / 큐 : 배열) 일반적으로

배열 자료형
배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리공간을 할당받는 작업 수행하는 자료형

배열의 경우 조회가 O(1)로 가능

동적배열
배열의 크기를 미리 지정하지 않고 자동으로 조절할 수 있는 = 자동으로 리사이징하는 배열인 동적 배열 등장
원리 : 미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면, 늘려주고 모두 복사하는 식. / 대개는 더블링이라 하여 2배씩 늘려주는데 각 언어마다 비율 상이

파이썬의 경우
재할당 비율 (Growth Factor) 초반에는 2배씩 전체적으로 1.125배 (초반 4 기준)
자바의 ArrayList : 1.5
C++ std:vector / Ruby : 2배

동적배열의 경우 크기 지정할 필요 없고 조회도 O(1)가능, 그러나 더블링이 필요할 만큼 공간이 차게되면 새로운 메모리 공간에 더 큰 크기의 배열을 할당하고 기존 데이터를 복사하는 작업이 필요하므로 O(n)비용이 발생
즉, 최악의 경우 삽입 시 O(n)이 되지만 자주 일어나는 일은 아님 -> 분할상환분석에 따른 입력시간은 여전히 O(1)

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q7. 두 수의 합

Q. 덧셈하여 타겟을 만들 수 있는 배열 두 숫자 인덱스르 리턴

입력

nums = [2,7,11,15], target = 9

출력

[0,1]

ex) nums[0] + nums[1] = 9

1) 부르트 포스

def twoSum(self, nums: List[int], target: int) -> List[int]:
  for i in range(len(nums)):
    for j in range(i+1, len(nums)):
      if nums[i] + nums[j] == target:
       return [i,j]

시간 복잡도 : O(n^2)
너무 느림

2) in을 이용한 탐색
모든 조합을 비교하지 않고 타겟에서 첫번째 값을 뺀 target-n이 존재하는지 탐색

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)]

O(n^2)이지만 in연산이 가볍고 빠름

3) 첫번째 수를 뺸 결과 키 조회

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 num_map and i != nums_map[target-num]:
      return [i, nums_map[target-num]]

O(n)가능

4) 조회 구조 개선 (풀이3 개선)

def twoSum(self, nums: List[int], target: int) -> List[int]:
  nums_map = {}
  for i,num in enumerate(nums):
    if target-num in nums_map:
      return [nums_map[target-num], i]
   nums_map[num] = i

5) 투 포인터 이용
불가능! (nums가 정렬되어있지 않기 때문, 만약 정렬하면 인덱스가 꼬여버림, 문제가 인덱스를 묻고 있기 때문에 불가능)

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q8. 빗물 트래핑

Q>높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산

입력

[0,1,0,2,1,0,1,3,2,1,2,1]

출력

6

1) 투 포인터를 최대로 이동

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:
      volulme += right_max – height[right]
      right -= 1
  return volume

풀이

[0,1,0,2,1,0,1,3,2,1,2,1]
(left, right) : (leftmax, rightmax)
(0,11)        : (0,1) -> volume : 0 + 0 - 0 / left + 1
(1,11)        : (1,1) -> volume : 0 + 1 - 1 / left + 1
(2,11)        : (1,1) -> volume : 0 + 1 - 0 / left + 1
(3,11)        : (2,1) -> volume : 1 + 1 - 1 / right - 1
(3,10)        : (2,2) -> volume : 1 + 2 - 2 / left + 1
(4,10)        : (2,2) -> volume : 1 + 2 - 1 / left + 1
(5,10)        : (2,2) -> volume : 2 + 2 - 0 / left + 1
(6,10)        : (2,2) -> volume : 4 + 2 - 1 / left + 1
(7,10)        : (3,2) -> volume : 5 + 2 - 2 / right -1
(7,9)          : (3,2) -> volume : 5 + 2 - 1 / right -1
(7,8)          : (3,2) -> volume : 6 + 2 - 2 / right -1
(7,7) //끝
return volume = 6

2) 스택 쌓기

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()
  return volume

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q9. 세 수의 합

Q.배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트 출력

입력

nums = [-1, 0, 1, 2, -1, -4]

출력

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

1) 부르트 포스

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
    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

-> 타임 아웃

2) 투포인터

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
ㅤ
    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: 
        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

풀이

i = 0~3
ㅤ
[-4, -1, -1, 0, 1, 2]
ㅤ
1) i = 0
left, right = (1, 5)
sum = -4 + -1 + 2 = -3
left + 1
ㅤ
left,right = (2,5)
sum = -4, -1 + 2 = -3
left + 1
ㅤ
left,right = (3,5)
sum = -4, 0, +2 = -2
ㅤ
left, right = (4,5)
sum = -4, 1, 2 = -1
ㅤ
left, right (5,5)
ㅤ
ㅤ
[-4, -1, -1, 0, 1, 2]
ㅤ
2) i = 1
left, right = (2,5)
sum = -1, -1, 2 = 0
append (-1,-1,2)
ㅤ
left + 1 / right -1 / (3,4)
sum = -1, 0, 1
append(-1,0,1)
ㅤ
3) i = 2 // 생략
ㅤ
4) i = 3
left, right (4,5)
sum = 3
// 끝
ㅤ
ㅤ
-> 투 포인터 슬라이딩윈도우랑 비슷

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q10. 배열 파티션1

Q.n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수

입력

[1,4,3,2]

출력

[4]

설명

n = 2 / 최대합 4
min(1,2), min(3,4) = 4

1) 오름차순 풀이

def arrayPairSum(self, nums: List[int]) -> int:
  sum = 0
  pair = []
  nums.sort()
ㅤ
  for n in nums:
    pair.append(n)
    if len(pair) == 2:
      sum += min(pair)
      pair = []
ㅤ
  return sum

2) 짝수 번째 값 계산

def arrayPairSum(self, nums: List[int] ) -> int:
  sum = 0
  nums.sort()
ㅤ
  for i, n in enumerate(nums):
    if i % 2 == 0:
     sum += n
  return sum

3) 파이썬다운 방식

def arrayPairSum(self, nums: List[int]) -> int:
  return sum(sorted(nums)[::2])

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q11. 자신을 제외한 배열의 곱

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

입력

[1,2,3,4]

출력

[24,12,8,6]

*주의 : 나눗셈을 하지 않고 O(n)에 풀이

1) 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈

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, -1, -1):
    out[i] = out[i] * p
    p = p* nums[i]
  return out

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q12. 주식을 사고팔기 가장 좋은 시점

Q. 한 번의 거래로 낼 수 있는 최대 이익을 산출

입력

[7,1,5,3,6,4]

출력

[5]

설명 : 1일 때 사서 6일 때 팔면 5의 이익을 얻음

1) 브루트 포스

ㅤ

def maxProfit(self, 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)
ㅤ
  return max_price

-> 타임아웃

2) 지점과 현재 값과의 차이 계산

def maxProfit(self, 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