[ch_07]배열

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ]

---

* 리스트 -> 숫자와 인덱스 둘 다 사용할 경우, enumerate 활용

 + nums[i] : 인덱스 로 숫자 접근

 + nums.index(n) : 숫자 로 인덱스 접근

---

* 브루트 포스 ->  in 과 해시테이블로 시간 단축

- 딕셔너리로 해시 테이블 : key =숫자, value = 인덱스

 -> target 에서 뺀 수가 딕셔너리에 있는지 확인, value 출력

# 더해서 target 이 되는 두 수의 인덱스

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

nums_map = {}
for i,num in enumerate(nums):

    if target-num in nums_map:
        print([nums_map[target-num],i])
    nums_map[num] = i

---

* 빗물 트래핑 (leetcode 42번)

- 투 포인터 + 왼쪽,오른쪽 최대 높이 

- 최대 높이 중 더 높은 쪽으로 투 포인터는 이동

- 투 포인터 이동하면서 최대 높이와의 차이만큼 부피가 추가

 

+ 리스트 비어있는지 확인 = if list / if not list

  def trap(self, height: List[int]) -> int:
      if not height:
          return 0

---

** 투 포인터 : 주로 정렬된 배열을 대상으로 한다. 

-> 합 구하거나, ...투 포인터 사용할 때 배열된 상태에서 하는게 더 좋지 않을지 생각해보자

---

* min(a,b)=c 인 pair 들에서, c 들의 합이 최대가 되게 하는 pair 들 (leetcode 561)

- sort 하는 것의 의미 먼저 생각해보기

 -> min(1,2) + min(3,4) = 1 + 3 = 4
 -> min(1,4,) + min(2,3) = 1 + 2 = 3
...정렬된 상태에서 묶는 게 그나마 큰 숫자들을 낭비?하지 않고 사용할 수 있는 것 같다
..여기서는 3을 4와 묶어서 낭비하지 않았다.

# 10 번 - 두 수 중 min 들로 구성된 합이 max 이려면....
nums = [2,1,3,4]

part = []
res = 0
nums.sort()

for n in nums:
    part.append(n)
    
    if len(part) == 2:
        res += min(part)
        part = []
        
print(res)

- 더 발견할 수 있는 규칙 : 짝수 번째 수들의 합

..정렬된 상태, 두 개씩 순서대로 pair 가 생기면,그 중 min 은 첫번째 즉 리스트의 짝수번째 숫자들

nums = [6,2,6,5,1,2]
print(sum(sorted(nums)[::2]))

---

* 두 수간의 차이가 가장 클 때의 차이(leetcode 121)

- brute force < 최소값과 최대 차이 와 리스트의 요소들을 비교 

prices = [7,1,5,3,6,4]
# 최저값 과 이익 갱신
profit = 0
min_price = sys.maxsize # 최소값을 바로 갱신되게 설정 

for n in prices:
    min_price = min(n, min_price)
    profit = max(profit, n-min_price)

- 이중 for 문을 반복하는 brute force 형태 -> n 을 최소값, profit 과만 비교