Ch.2 배열과 문자열
면접 실전: Top 5 배열 문제
FAANG 면접에서 가장 많이 나오는 배열 문제 5선
Two Sum, Best Time to Buy and Sell Stock, Product of Array Except Self, Contains Duplicate, Maximum Subarray — 이 5문제만 완벽하면 배열은 합격!
문제마다 요구하는 기법이 다르다. 어떤 패턴을 써야 할까?
해시맵, Kadane, Prefix Product 등 핵심 패턴을 하나씩 정복합시다!
핵심 내용
LeetCode #1번, 면접 단골 중의 단골! Two Sum을 해시맵으로 O(n)에 풀어봅시다
Two Sum: 배열에서 합이 target인 두 수의 인덱스를 반환 예) nums = [2, 7, 11, 15], target = 9 출력: [0, 1] (2 + 7 = 9)
def two_sum(nums, target):
seen = {} # 값 → 인덱스 매핑
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]핵심: 해시맵으로 complement 조회 O(1) → 전체 O(n)
주식 한 번 사고 한 번 팔아서 최대 이익을 구하라!
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
print(max_profit([7, 1, 5, 3, 6, 4])) # 5 (1에 사서 6에 팔기)나눗셈 없이! 자기 자신을 제외한 나머지의 곱을 구하라
def product_except_self(nums):
n = len(nums)
result = [1] * n
# 왼쪽 누적곱
left = 1
for i in range(n):
result[i] = left
left *= nums[i]
# 오른쪽 누적곱
right = 1
for i in range(n - 1, -1, -1):
result[i] *= right
right *= nums[i]
return result
print(product_except_self([1, 2, 3, 4])) # [24, 12, 8, 6]핵심: 왼쪽 누적곱 × 오른쪽 누적곱 = 자기 제외 전체 곱. O(n) 시간, O(1) 추가 공간
마지막 두 문제! Contains Duplicate와 Maximum Subarray
# ④ Contains Duplicate — 해시 셋 O(n)
def contains_duplicate(nums):
return len(nums) != len(set(nums))
print(contains_duplicate([1, 2, 3, 1])) # True
# ⑤ Maximum Subarray — Kadane's Algorithm O(n)
def max_subarray(nums):
max_sum = current = nums[0]
for num in nums[1:]:
current = max(num, current + num) # 이어가기 vs 새로 시작
max_sum = max(max_sum, current)
return max_sum
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6 ([4,-1,2,1])Top 5 정리 | 문제 | 패턴 | 시간 | |---|---|---| | Two Sum | 해시맵 | O(n) | | Buy & Sell Stock | 최소값 추적 | O(n) | | Product Except Self | 좌우 누적곱 | O(n) | | Contains Duplicate | 해시 셋 | O(n) | | Maximum Subarray | Kadane | O(n) |
Two Sum에서 해시맵의 역할은?
Kadane's Algorithm의 핵심 아이디어는?
Product of Array Except Self는 나눗셈을 사용해야만 풀 수 있다
Best Time to Buy and Sell Stock은 O(n)에 풀 수 있다
Top 5 배열 문제 정복
정리 노트
면접 실전 — Top 5 배열 문제
문제별 핵심 패턴
- Two Sum
- 해시맵 — complement O(1) 조회
- Buy & Sell Stock
- 최소값 추적 — 한 번 순회 O(n)
- Product Except Self
- 좌우 누적곱 — 나눗셈 없이 O(n)
- Contains Duplicate
- set — len 비교 O(n)
- Maximum Subarray
- Kadane — 이어가기 vs 새로 시작
이 5문제만 완벽하면 배열 면접은 걱정 없습니다!
시각 자료
핵심 정리
- 1Two Sum: 해시맵 O(n)
- 2Buy & Sell Stock: 최소값 추적 O(n)
- 3Product Except Self: 좌우 누적곱 O(n)
- 4Contains Duplicate: set O(n)
- 5Maximum Subarray: Kadane O(n)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작