TIL) 구글 코딩 인터뷰 풀이 : Spike!

https://www.youtube.com/watch?v=XKu_SEDAykw&t=430
해당 영상을 보고 풀이 과정을 기록한 코드입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
# 문제
# collection of numbers
# find matching pair equal to sum(given)
# [1,2,3,9]  sum 8
# [1,2,4,4]  sum 8
 
# 매칭 pair 없는 경우도 있음
# memory에 있고, ordered된 상태(ascending)
# repeating element? : 같은 인덱스에 있는 값 재활용 불가능
# 다른 인덱스에 같은 값은 나올 수 있음
# int, 마이너스도 가능
 
# nested for loop 사용 가능 i Loop과 i+1 Loop
# 그러나 O(n^2) 이기에 time consuming함 
 
# 1이라고 치면, 7을 찾으면 되는데.. sorted 돼있기에 binary search하면 된다
# log algorithm 
# 아직 좀 느림
 
ex = [1,2,3,4,4]
 
def binary_search(array, left, right, ele):
  if right >= left:
    mid = (left+right)//2
    if array[mid] == ele:
      return True
    elif array[mid] > ele:
      return binary_search(array,left,mid-1, ele)
    else:
      return binary_search(array,mid+1, right, ele)
  else:
    return False
    
def slightly_better_pair_sum(array,sum):
  for i in range(len(array)):
    comp=sum-array[i]
    if binary_search(array,i+1,len(array)-1,comp):
      return "yes"
  return "No"
 
# 단방향인 binary search보다 
# 가장 큰 sum은 마지막 두 값일 것임
# 가장 작은 sum은 첫 두 값
# 그러니깐, 첫번째 값보다 작은 것은 없고, 마지막 값보다 큰 것은 없음
# range를 가운데로 줄여가며 linear하게 접근
 
# binary search를 하게된다면, 각 element마다 binary search를 반복해야 하는 반면, 이렇게하면 한번의 흐름으로 끝남
 
# python으로 해보자
def findSumPair(array,sum):
  left = 0
  right = len(array)-1
  while right>left:
    if array[left] + array[right] == sum:
      return "yes"
    elif array[left] + array[right] < sum:
      left += 1
    else:
      right -= 1
  return "No"
 
 
# print(findSumPair([1,2,4,4],8))
# O(n) 의 시간 복잡도 
 
 
# sorted 돼있지 않다면? - error check
# sort 한 이후 해당 코드 반복
 
def SortPairSum(array,sum):
  array.sort()
  left = 0
  right = len(array) -1
  while right>left:
    if array[left] + array[right] == sum:
      return "yes"
    elif array[left] + array[right] < sum:
      left += 1
    else:
      right -= 1
  return "No"
 
# print(findSumPair([4,5,2,3,7],8))
 
# 개선점
# O(nlog n)의 시간복잡도
# O(n) 으로 돌아가기 위하여 
  # array를 가면서 만나는 요소를 딕셔너리에 넣음
  # 현재 요소의 complement(요소와 더해서 sum되는 것)없다는 것은
  # array를 loop하면서 현재 요소의 complement가 딕셔너리에 있는지 확인하고
  # 있으면 yes를 리턴
  # 없으면 no를 리턴하고 현재 element를 딕셔너리에 더함
 
def smartestPairSum(array,sum):
  dictionary = dict()
  for item in array:
    comp = sum - item
    if not comp in dictionary:
      dictionary[item] = True
    else:
      return "YES"
  return "No"
 
print(smartestPairSum([4,5,2,3,7],8))
# 더해서 sum이 되는
# complement1 , complment2이 있을때,
# 먼저 나온 complement1을 기록해두었다가, 이후에 complemnet2 가 나오면 딕셔너리에서 이를 찾아서 합이 되는 수가 있음을 return 하고 끝냄.
# array개수만큼 operation이 늘어나기에 O(n)임
Colored by Color Scripter
cs
참조 : https://github.com/VicodinAbuser/ZTM-DS-and-Algo-Python/blob/master/venv/Scripts/How%20to%20solve%20coding%20problems/Google%20Interview%20Question.py