language : python3
https://leetcode.com/problems/two-sum/
나의 생각
모든 경우의 수 다 조사하기
풀이 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]
풀이 2) in을 이용한 탐색
- 모든 조합을 비교하지 않고 정답, 즉 타겟에서 첫 번째 값을 뺀 값 target - n이 존재하는지 탐색하는 문제로 변경해보자.
- 시간복잡도:
`in`의 시간 복잡도는 O(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)]
풀이 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 nums_map and i != nums_map[target - num]:
return [i, nums_map[target - num]]
풀이 4) 조회 구조 개선
- 딕셔너리 저장과 조회를 2개의 for 문으로 각각 처리했던 방식을 개선해서 하나의 for문으로 합치기
- 전체를 저장할 필요 없이 정답을 찾게 되면 함수를 바로 빠져나올 수 있다.
- 단점: 두 번째 값을 찾기 위해 매번 비교해야 하기 때문에 성능 이점을 크게 없다.
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_map = {}
# 하나의 for 문으로 통합
for i, num in enumerate(nums):
if target - num in nums_map:
return [nums_map[target - num], i]
nums_map[num] = i
풀이 5) 투 포인터 활용
⚠ 이 문제는 투 포인터를 쓸 수 없다!!
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 정렬하고 써야하는데 정렬하면 인덱스가 엉망이 되므로 사용할 수 없는 풀이
left, right=0, len(nums) - 1
while not left == right:
# 합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로
if nums[left] + nums[right] < target:
left += 1
elif nums[left] + nums[right] > target:
right -= 1
else:
return [left, right]
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, n in enumerate(nums):
for j in range(i+1, len(nums)):
if target - n == nums[j]:
return [i, j]
https://leetcode.com/problems/trapping-rain-water/
나의 생각
2차원 행렬로 전환한다
풀이 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:
# 최대 높이의 막대까지 각각 좌우로 기둥 최대 높이 left_max, right_max가
# 현재 높이와의 차이만틈 물 높이 volume을 더해 나간다.
volume += left_max - height[left]
left += 1
else:
volume += right_max - height[right]
right -= 1
return volume
풀이 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
water = min(height[i], height[stack[-1]]) - height[top]
volume += distance * water
stack.append(i)
return volume
def trap(self, height: List[int]) -> int:
left, right = 0, len(height)-1
volume = 0
left_max, right_max = height[left], height[right]
while(left < right):
left_max = max(height[left], left_max)
right_max = max(height[right], right_max)
if left_max <= right_max:
volume += left_max - height[left]
left += 1
else:
volume += right_max - height[right]
right -= 1
return volume
https://leetcode.com/problems/3sum/
나의 생각
브루트포스
풀이 1) 브루트 포스로 계산
⚠타임아웃
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = []
nums.sort()
# 브루트포스 n^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
풀이 2) 투 포인터로 합 계산
- i를 축으로 하고, 중복된 값을 건너뛰게 한 부분은 이전 풀이와 동일하게 한다.
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
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
# 간격을 좁혀가며 합 sum 계산
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
def threeSum(self, nums: List[int]) -> List[List[int]]:
size = len(nums)
if size < 3:
return []
nums.sort()
answer = []
for i in range(0, size-2):
if 1 <= i and nums[i-1] == nums[i]:
continue
for j in range(i+1, size-1):
if j-i > 1 and nums[j-1] == nums[j]:
continue
for k in range(j+1, size):
if k-j > 1 and nums[k-1] == nums[k]:
continue
if nums[i] + nums[j] + nums[k] == 0:
# if i != j and i != k and j != k:
# if([nums[i], nums[j], nums[k]] not in answer):
answer.append([nums[i], nums[j], nums[k]])
return answer
2) sum 활용https://leetcode.com/problems/array-partition-i/
나의 생각
브루트포스
풀이 1) 오름차순 풀이
- min()을 합산했을 때 최대를 만드는 것은 결국 min()이 되도록 커야 한다는 뜻
- 뒤에서부터 내림차순으로 집어넣으면 항상 최대 min() 페어를 유지할 수 있다.
- 문제의 배열 입력값은 항상 2n개일 것이므로 앞에서부터 오름차순으로 집어넣어도 결과는 같을 것이다
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) 짝수 번째 값 계산
- 페어에 대해 일일이 min() 값을 구하지 않아도 짝수 번째 값(0부터 시작하므로)을 더하면 됨
- 정렬된 상태에서는 짝수 번째에 항상 작은 값이 위치하기 때문
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) 파이썬다운 방식
- 슬라이싱 구문
[::2]
는 2칸씩 건너뛰므로 짝수 번째를 계산하는 것과 동일하다
def arrayPairSum(self, nums: List[int]) -> int:
return sum(sorted(nums)[::2])
https://leetcode.com/problems/product-of-array-except-self/
나의 생각
모름
자기 자신을 제외하고 왼쪽의 곱셈 결과와 오른쪽의 곱셈 결과를 곱하는 풀이 하나뿐이다.
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, 0-1, -1):
out[i] = out[i] * p # 왼쪽 곱셈 결과 * 우측 곱셈 결과
p = nums[i] * p # 우측 곱셈 결과
return out
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
나의 생각 (success)
마지막 날짜부터 거꾸로 계산
현재 날짜의 주식값과 비교하며 max값 갱신
시스템의 가장 큰 값 : sys.maxsize
시스템의 가장 작은 값 : -sys.maxsize
23장 86번 '최대 서브 배열' 문제와 유사함.
86번 문제를 카데인 알고리즘(Kadane's Algorithm)으로 O(n) 풀이 가능함
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
def maxProfit(self, prices: List[int]) -> int:
maxV = prices[-1]
answer = 0
for i in range(len(prices)-2, 0-1, -1):
maxV = max(maxV, prices[i])
answer = max(answer, maxV-prices[i])
return answer