language : python3
배열
- (C 기준)배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형
- but 배열의 크기를 미리 지정하지 않고 자동으로 조정할 수 있는 배열인 동적 배열 등장
- 파이썬은 동적 배열만 지원한다. 정적 배열 자체가 없다.
문제
07. 두 수의 합
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) 투 포인터 활용
⚠ 이 문제는 투 포인터를 쓸 수 없다!!
- 왼쪽 포인터와 오른쪽 포인터의 합이 타겟보다 크다면 오른쪽 포인터를 왼쪽으로, 작다면 왼쪽 포인터를 오른쪽으로 옮기면서 값을 조정하는 방식
- 시간복잡도
- 단점: nums가 정렬된 상태가 아님. 그래서 정렬하고 써야 함. but 인덱스 정렬하면 정답으로 인덱스를 반환할 때 엉망이 됨. 따라서 정답 아님.
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]
08. 빗물 트래핑
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
09. 세 수의 합
https://leetcode.com/problems/3sum/
나의 생각
브루트포스
정답
풀이 1) 브루트 포스로 계산
⚠타임아웃
- 앞 뒤에 같은 값이 있을 수 있으므로 먼저 정렬함
- 정렬 시간복잡도
- i, j, k 각각의 포인터가 계속 이동하면서 i+j+k=0을 찾아낸다
- 중복된 값이 있을 수 있으므로 이 경우 continume로 건너뛰게 한다
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
- i의 다음 지점과 마지막 지점을 left, right로 설정하고 간격을 좁혀가며 sum을 계산한다
- sum이 0보다 작다면 값을 더 키워야 하므로 left를 우측으로 이동
- sum이 0보다 크다면 값을 작게 하기 위해 right를 좌측으로 이동
- sum이 0 이면 정답이므로 results에 추가
- 추가한 다음에는 left, right 양 옆에 동일한 값이 있을 수 있으므로 left += 1, right -= 1을 반복해서 스킵하도록 처리한다
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- 투 포인터 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략. 범위를 좁혀 나가기 위해서는 일반적으로 배열이 정렬되어 있을 때 유용하다. 2개의 포인터가 좌우로 자유롭게 움직이며 문제를 풀이한다. 슬라이딩 윈도우(Sliding window)와 여러모로 비슷한 점이 많다.
- 나의 풀이 1) 브루트포스로 하면 시간초과 난다는것을 잊고 브루트포스로 했다가 다시 책봄...
2) sum 활용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
10. 배열 파티션 1
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])11. 자신을 제외한 배열의 곱
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 out12. 주식을 사고팔기 가장 좋은 시점
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
Java, Python