세 수의 합
- 리트코드 3번 문제 : https://leetcode.com/problems/3sum/
- 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.
- 입력 : nums = [-1, 0, 1, 2 ,-1, -4]
- 출력 : [[-1, 0, 1], [-1, -1, 2]]
- 설명 : -1 + 0 + 1 = 0, (-1) + (-1) + 2 = 0
풀이 1) 투 포인터 응용
- 실행 속도 : 888 ms
- 리스트를 오름차순을 정렬한 후, 차례로 원소를 기준으로하여, 기준 우측의 리스트에서 투 포인터 방식을 취합니다.
- 이럴 경우 기준이 되는 수가 중복될 경우, 그 기준으로 합이 0이 되는 두 수가 우측에 있을 경우 중복되어 발견되므로, 예외처리를 해주어야합니다.
- 또한 기준 우측의 리스트 내에서 투 포인터를 취하는데, 이때도 투 포인터 내에서 기준이 되는 수가 중복이 발생할 경우, 결과가 중복되어지므로 예외처리를 해주어야합니다.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result: List = []
for index in range(len(nums) - 2):
if index > 0 and nums[index] == nums[index-1]:
continue
left, right = index + 1, len(nums) - 1
while left < right:
sum = nums[index] + nums[left] + nums[right]
if sum < 0:
left += 1
elif sum > 0:
right -= 1
else:
result.append([nums[index], 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 result
solution = Solution()
test_case: List[int] = [-1,0,1,2,-1,-4]
result: List[List[int]] = solution.threeSum(test_case)
print(result) 배열 파티션 I
- 리트코드 561번 문제 : https://leetcode.com/problems/array-partition-i/
- n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.
- 입력 : nums = [1, 4, 3, 2]
- 출력 : 4
- 설명 : min(1,2) + min(3, 4) = 1 + 3 = 4
풀이 1) 짝수번째 값 계산
- 실행 시간 : 284 ms
- min(pair)의 합이 클려면 결국 큰 수끼리 pair를 구성하여야 함을 알 수 있고, 따라서 주어진 수들을 오름차순을 정렬한다.
- 오름차순으로 정렬한 후 2개를 한 쌍으로 묶을 경우 짝수번째에 min(pair)가 위치하므로, 짝수번째의 수만 더해주는 방식.
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
return sum(sorted(nums)[::2]) # 오름차순 정렬한 nums의 짝수번째 element만 더함.
solution = Solution()
test_case: List[int] = [1, 4, 3, 2] # 테스트 케이스
result: int = solution.arrayPairSum(test_case)
print(result) # 결과 : 4자신을 제외한 배열의 곱
- 리트코드 238번 문제 : https://leetcode.com/problems/product-of-array-except-self/
- 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라.
- 입력 : nums = [1, 2, 3, 4]
- 출력 : [24, 12, 8, 6]
- 설명 : [2 x 3 x 4, 1 x 3 x 4, 1 x 2 x 4, 1 x 2 x 3]
풀이 1) 좌측 곱, 우측 곱 나누어 구하기.
- 자신의 제외한 수의 곱 중 우측곱, 좌측곱을 나누어 계산한 뒤, 최종적으로 우측곱과 좌측곱을 곱합니다.
- 위 입력을 기준으로하면 좌측 곱이 이루는 리스트는 [1, 1, 2, 6], 우측 곱이 이루는 리스트는 [24, 12, 4, 1], 두 리스트는 각 요소끼리 곱하면 [24, 12, 8, 6]
- 단, 양 끝의 경우는 좌측과 우측이 없으므로 곱해도 지장 없는 1(num)을 넣는다.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
result: List[int] = []
num:int = 1
for index in range(len(nums)):
result.append(num)
num *= nums[index]
num = 1
for index in range(len(nums) - 1, 0 - 1, -1):
result[index] *= num
num *= nums[index]
return result
solution = Solution()
test_case: List[int] = [1, 2, 3, 4]
result: List[int] = solution.productExceptSelf(test_case)
print(result) # 결과 : [24, 12, 8, 6]주식을 사고팔기 가장 좋은 시점
- 리트코드 561번 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock
- 한 번의 거래로 낼 수 있는 최대 이익을 산출하라.
- 입력 : prices = [7, 1, 5, 3, 6, 4]
- 출력 : 5
- 설명 : 1일 때 사서, 6일 때 팔면 5의 이익 발생
풀이 1) 증가 지점 기준 최대 이익 갱신
- 실행 속도 : 72 ms
- 주식의 값이 증가하는 기점에서 주식을 산 이후, 그 이후 기점의 가격과의 이익을 계산하여 최대 이익을 갱신하는 방식 ( 감소 구간으로 접어들 경우, 구간 점프 )
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
max_profit: int = 0
left, right = 0, 1
while left < len(prices) - 1 and right < len(prices):
if prices[left] > prices[right]:
left += 1
right = left + 1
else:
max_profit = max(max_profit, prices[right] - prices[left])
right = right + 1
return max_profit
solution = Solution()
test_case: List[int] = [7,1,5,3,6,4]
result: int = solution.maxProfit(test_case)
print(result)풀이 2) 최저기점 갱신, 최저기점 기준 최대이익 갱신
- 실행 속도 : 60 ms
- 최저기점을 계속 갱신하며, 해당 기점을 기준으로 최대이익 갱신
class Solution:
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 # 반환
Java, Python, JavaScript Lover