📌 7) 두 수의 합 ( 리트코드 1. Two Sum )
✔ 풀이 (브루트 포스)
class Solution(object):
def twoSum(self, nums, target):
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]=> 시간 복잡도 O(n2)
✔ 풀이 (in을 이용한 탐색)
class Solution(object):
def twoSum(self, nums, target):
for i in range(len(nums)-1):
num = target - nums[i] #i인덱스 다음 인덱스부터 끝까지 나머지 리스트에
if num in nums[i+1:]: #더해서 타겟이 되는 값 있는지 확인
return [i, nums[i+1:].index(num) + (i + 1)]=> 시간 복잡도 O(n2) , 하지만 in은 파이썬 레벨에서 매번 값을 비교하는 것에 비해 훨씬 더 빨리 실행됨.
✔ 풀이 (첫 번째 수를 뺀 결과 키 조회)
비교나 탐색 대신 한 번에 정답을 찾을 수 있는 방법은? 딕셔너리 사용!
=> 딕셔너리는 해시 테이블로 구현되어 있고, 이 경우 조회는 평균적으로 O(1)에 가능.
class Solution(object):
def twoSum(self, nums, target):
nums_dic = {} #nums_dic = [값 : 인덱스, ...]
for idx, num in enumerate(nums):
nums_dic[num] = idx
for idx, num in enumerate(nums):
if target - num in nums_dic and idx != nums_dic[target - num]:
return [idx, nums_dic[target - num]]=>분할 상환 분석에 따른 시간 복잡도는 O(1) 이며, 전체는 O(n)이 된다.
✔ 풀이 (조회 구조 개선)
#초기 내가 생각했던 방법
#class Solution(object):
# def twoSum(self, nums, target):
# nums_dic = {} #nums_dic = [값 : 인덱스, ...]
# for idx, num in enumerate(nums):
# nums_dic[num] = idx
# if target - num in nums_dic and idx != nums_dic[target - num]:
# return [idx, nums_dic[target - num]]
# = > nums = [3, 3] / target = 6인 case 통과 X
class Solution(object):
def twoSum(self, nums, target):
nums_dic = {} #nums_dic = [값 : 인덱스, ...]
for idx, num in enumerate(nums):
if target - num in nums_dic and idx != nums_dic[target - num]:
return [idx, nums_dic[target - num]]
nums_dic[num] = idx
#비교후에 nums_dic[num] = idx을 추가해줌으로써, 같은 값을 더해 target이 되는 경우에
#겹치지 않는 인덱스를 return 할 수 있다.✔ 풀이 (투 포인터 사용)
class Solution(object):
def twoSum(self, nums, target):
#각 두개의 포인터의 합이 target보다 작으면 왼쪽포인터를 오른쪽으로 이동,
#target보다 크면 오른쪽 포인터를 왼쪽으로 이동
#단, nums가 정렬되어 있어야함
nums.sort() #정렬 => 인덱스 값 섞임
left, right = 0, len(nums) - 1
while left < right:
if nums[left] + nums[right] < target:
left += 1
elif nums[left] + nums[right] > target:
right -= 1
else:
return [nums[left], nums[right]]
#해당 문제에선 인덱스를 반환해야 하기 때문에 다음과 같은 방식으로 풀면 안됨
#값을 반환하는 문제이면 다음과 같은 방법을 사용할 수 있음=> 시간 복잡도 O(n)
📌 8) 빗물 트래핑 ( 리트코드 42. Trapping Rain Water )
✔ 풀이 (투 포인터 사용)
#최대 높이는 부피에 영향 주지 X
#그저 왼쪽과 오른쪽 가르는 역할!
class Solution(object):
def trap(self, height):
if not height: #[]인 경우
return 0
volume = 0
left, right = 0, len(height) - 1
max_left, max_right = height[left], height[right]
while left < right:
max_left = max(max_left, height[left])
max_right = max(max_right, height[right])
#더 높은 쪽을 향해 투 포인트 이동
#=> 높이가 최대인 지점에서 투 포인트 만남
if max_left <= max_right:
volume += max_left - height[left]
left += 1
else:
volume += max_right - height[right]
right -= 1
return volume=> 시간 복잡도 O(n)
✔ 풀이 (스택 쌓기)
#최소 3개의 구간이 존재해야 물이 고일 수 있는 환경이 만들어짐
#현재 높이가 이전 높이보다 클 경우
#3개의 구간을 잡고, 해당구간으로 만들어 지는 물의 부피를 더해준다
#-> top = stack.pop() 하면 3개의 구간의 인덱스는 stack[-1], top, i(현재)
#-> 물의 부피는 가로*세로
class Solution(object):
def trap(self, height):
volume, stack = 0, []
for i in range(len(height)):
#stack에 있는 인덱스들의 높이가 현재의 높이보다 작을 경우 계속 반복
while stack and height[i] > height[stack[-1]]:
top = stack.pop() #중간 구간
#stack이 비어있는 경우(=3개의 구간을 만들 수 없는 경우) 빠져나감
if not stack:
break
#처음 구간 stack[-1] / 중간구간 top / 마지막구간 i
width = i - stack[-1] - 1 #가로
length = min(height[i], height[stack[-1]]) - height[top] #높이
volume += width * length
stack.append(i)
return volume
=> 시간 복잡도 O(n)
📌 9) 세 수의 합 ( 리트코드 15. 3Sum )
✔ 풀이 (부르트 포스)
class Solution(object):
def threeSum(self, nums):
result = []
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:
result.append([nums[i], nums[j], nums[k]])
return result=> 시간초과
=> 시간 복잡도 O(n3)
✔ 풀이 (투 포인터)
class Solution(object):
def threeSum(self, nums):
result = []
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:
result.append([nums[i], nums[left], nums[right]])
#정답에 중복이 들어가면 X => 중복처리
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 result=> 시간 복잡도 O(n2)
📌 10) 배열 파티션1 ( 리트코드 561. Array Partition 1)
✔ 풀이 (오름차순 풀이)
class Solution(object):
def arrayPairSum(self, nums):
pair, sum = [], 0
nums.sort()
for num in nums:
pair.append(num)
if len(pair) == 2:
sum += min(pair)
pair = []
return sum=> 시간 복잡도 O(n)
✔ 풀이 (짝수 번째 값 계산)
class Solution(object):
def arrayPairSum(self, nums):
nums.sort()
sum = 0
for idx, num in enumerate(nums):
if idx % 2 == 0: #짝수 인덱스일 경우
sum += num
return sum=> 시간 복잡도 O(n)
✔ 풀이 (파이썬 다운 방식)
class Solution(object):
def arrayPairSum(self, nums):
return sum(sorted(nums)[::2])=> 시간 복잡도 O(n)
📌 11) 자신을 제외한 배열의 곱 ( 리트코드 238. Product of Array Except Self )
- 해당 문제를 보자마자 생각나는 풀이는 전체를 곱한 수에 각 인덱스에 존재하는 값들로 나누어 해당 인덱스에 덮어씌우는 풀이이다.
=> 나눗셈을 하지 않고 O(n)에 풀이하는 방법은?
✔ 풀이
class Solution(object):
def productExceptSelf(self, nums):
#out = 현재위치 i를 제외한 배열의 곱
out = []
#현재위치 i를 제외한 왼쪽 배열의 곱
p = 1
for i in range(len(nums)):
out.append(p)
p *= nums[i]
#i를 제외한 오른쪽 배열의 곱을 out에 곱해줌
p = 1
for i in range(len(nums) - 1, -1, -1):
out[i] *= p
p *= nums[i]
return out=> 시간 복잡도 O(n)
📌 12) 주식을 사고팔기 가장 좋은 시점 ( 리트코드 121. Best Time to Buy and Sell Stock )
부르트 포스 말고 다른 풀이는?
✔ 풀이
# 최소 초기값 => sys.maxsize / float('inf')
# 최대 초기값 => -sys.maxsize / float('-inf')
class Solution(object):
def maxProfit(self, prices):
profit, min_price = 0, sys.maxsize
for price in prices:
min_price = min(min_price, price)
profit = max(profit, price - min_price)
return profit=> 시간 복잡도 O(n)
