FAANG 코딩 인터뷰 완전 정복: 배열과 문자열 핵심 패턴

FAANG(Facebook/Meta, Apple, Amazon, Netflix, Google) 코딩 인터뷰에서 배열과 문자열 문제는 전체 출제 비중의 40% 이상을 차지합니다. 이 글에서는 실제 인터뷰에서 자주 등장하는 6가지 핵심 패턴을 실전 코드와 함께 완전히 정복합니다.

1. Two Pointers 패턴

개념 및 언제 사용하는가

Two Pointers 패턴은 정렬된 배열이나 연결 리스트에서 두 개의 포인터를 사용해 선형 시간에 문제를 해결하는 기법입니다.

사용 조건:

정렬된 배열에서 두 원소의 합/차를 구하는 경우
배열의 양 끝에서 조건을 만족하는 쌍을 찾는 경우
중복 제거나 파티셔닝이 필요한 경우

핵심 아이디어: O(n^2) 브루트 포스를 O(n)으로 줄일 수 있습니다.

문제 1: Two Sum II (LeetCode 167)

정렬된 배열에서 두 수의 합이 target이 되는 인덱스를 찾아라.

def twoSum(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []  # 문제 조건상 항상 해가 존재

# 예시
# Input: numbers = [2,7,11,15], target = 9
# Output: [1,2]

시간 복잡도: O(n) - 각 포인터가 최대 n번 이동 공간 복잡도: O(1) - 추가 공간 불필요

FAANG 팁: 정렬되지 않은 배열이라면 HashMap을 사용한 O(n) 풀이를 먼저 제시하고, 정렬된 경우 Two Pointers가 더 공간 효율적임을 설명하세요.

문제 2: 3Sum (LeetCode 15)

배열에서 합이 0인 세 원소를 모두 찾아라 (중복 없이).

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []

    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:
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                result.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
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

# 예시
# Input: nums = [-1, 0, 1, 2, -1, -4]
# Output: [[-1, -1, 2], [-1, 0, 1]]

시간 복잡도: O(n^2) - 정렬 O(n log n) + 이중 루프 O(n^2) 공간 복잡도: O(1) ~ O(n) (정렬 알고리즘에 따라)

FAANG 팁: Meta 인터뷰에서 자주 출제됩니다. 중복 처리 로직을 빠뜨리지 않도록 주의하세요.

문제 3: Container With Most Water (LeetCode 11)

높이 배열이 주어질 때 가장 많은 물을 담을 수 있는 컨테이너의 용량을 구하라.

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        # 현재 물의 양 = 너비 * 더 낮은 높이
        width = right - left
        current_water = width * min(height[left], height[right])
        max_water = max(max_water, current_water)

        # 더 낮은 쪽 포인터를 이동 (더 높은 값을 찾기 위해)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

# 예시
# Input: height = [1,8,6,2,5,4,8,3,7]
# Output: 49

시간 복잡도: O(n) 공간 복잡도: O(1)

왜 이 방식이 최적인가? 더 낮은 높이의 벽을 이동하는 이유는, 더 높은 벽을 이동하면 너비도 줄고 높이도 줄거나 같아서 절대 더 많은 물을 담을 수 없기 때문입니다.

문제 4: Trapping Rain Water (LeetCode 42)

고난도 문제로 빗물을 가두는 총량을 구하라.

def trap(height: list[int]) -> int:
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0

    while left < right:
        if left_max <= right_max:
            left += 1
            left_max = max(left_max, height[left])
            # 현재 위치에서 담을 수 있는 물 = 왼쪽 최대 - 현재 높이
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]

    return water

# 예시
# Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
# Output: 6

시간 복잡도: O(n) 공간 복잡도: O(1) - prefix max 배열 없이 투 포인터로 해결

FAANG 팁: Google, Amazon 인터뷰 단골 문제입니다. DP 방식(O(n) space)도 알아두고, 투 포인터가 왜 더 효율적인지 설명할 수 있어야 합니다.

2. Sliding Window 패턴

개념

연속된 부분 배열/문자열에서 최적해를 찾는 패턴입니다. 윈도우를 슬라이딩하며 전체를 한 번만 순회합니다.

Fixed Window: 윈도우 크기가 고정된 경우 Variable Window: 조건에 따라 윈도우 크기가 변하는 경우

문제 5: Longest Substring Without Repeating Characters (LeetCode 3)

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        # 중복 문자가 있으면 왼쪽 포인터 이동
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

# 최적화 버전 (HashMap 사용)
def lengthOfLongestSubstringOptimized(s: str) -> int:
    char_index = {}
    left = 0
    max_length = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1

        char_index[char] = right
        max_length = max(max_length, right - left + 1)

    return max_length

# 예시
# Input: "abcabcbb"
# Output: 3 ("abc")

시간 복잡도: O(n) 공간 복잡도: O(min(n, charset_size))

문제 6: Minimum Window Substring (LeetCode 76)

문자열 s에서 t의 모든 문자를 포함하는 최소 윈도우를 찾아라.

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""

    need = Counter(t)
    missing = len(t)  # 아직 포함하지 못한 문자 수

    start = 0
    best_start = 0
    best_end = float('inf')

    left = 0
    for right, char in enumerate(s):
        # 필요한 문자라면 missing 감소
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        # 모든 문자를 포함했을 때 윈도우 최소화
        if missing == 0:
            # 왼쪽에서 불필요한 문자 제거
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1

            # 현재 윈도우가 더 작으면 업데이트
            if right - left < best_end - best_start:
                best_start = left
                best_end = right

            # 윈도우 축소 (다음 더 짧은 윈도우 탐색)
            need[s[left]] += 1
            missing += 1
            left += 1

    if best_end == float('inf'):
        return ""
    return s[best_start:best_end + 1]

# 예시
# Input: s = "ADOBECODEBANC", t = "ABC"
# Output: "BANC"

시간 복잡도: O(|s| + |t|) 공간 복잡도: O(|s| + |t|)

문제 7: Sliding Window Maximum (LeetCode 239)

크기 k인 슬라이딩 윈도우에서 각 위치의 최대값을 구하라.

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()  # 인덱스를 저장 (값의 감소 순서 유지)
    result = []

    for i, num in enumerate(nums):
        # 윈도우 밖으로 나간 인덱스 제거
        if dq and dq[0] < i - k + 1:
            dq.popleft()

        # 현재 값보다 작은 원소는 유용하지 않으므로 제거
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        # 윈도우가 완성되면 결과 추가
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# 예시
# Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
# Output: [3,3,5,5,6,7]

시간 복잡도: O(n) - 각 원소가 deque에 한 번씩 추가/삭제 공간 복잡도: O(k)

문제 8: Fruit Into Baskets (LeetCode 904)

최대 2종류의 과일만 담을 수 있는 바구니로 연속해서 따는 과일의 최대 개수를 구하라.

from collections import defaultdict

def totalFruit(fruits: list[int]) -> int:
    basket = defaultdict(int)
    left = 0
    max_fruits = 0

    for right, fruit in enumerate(fruits):
        basket[fruit] += 1

        # 3종류 이상이면 왼쪽 포인터 이동
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1

        max_fruits = max(max_fruits, right - left + 1)

    return max_fruits

# 예시
# Input: fruits = [1,2,1,2,3]
# Output: 4 ([1,2,1,2])

시간 복잡도: O(n) 공간 복잡도: O(1) - 최대 3가지 과일 종류만 저장

3. Binary Search 패턴

개념

정렬된 배열에서 O(log n) 시간에 원소를 탐색합니다. 표준 형태 외에도 다양한 변형이 FAANG 인터뷰에 등장합니다.

표준 Binary Search 템플릿:

def binarySearch(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2  # 오버플로우 방지

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

문제 9: Search in Rotated Sorted Array (LeetCode 33)

회전된 정렬 배열에서 타겟을 찾아라.

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # 왼쪽 절반이 정렬된 경우
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 오른쪽 절반이 정렬된 경우
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

# 예시
# Input: nums = [4,5,6,7,0,1,2], target = 0
# Output: 4

시간 복잡도: O(log n) 공간 복잡도: O(1)

문제 10: Find Minimum in Rotated Sorted Array (LeetCode 153)

def findMin(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        # mid가 right보다 크면 최소값은 오른쪽 절반에 있음
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    return nums[left]

# 예시
# Input: nums = [3,4,5,1,2]
# Output: 1

시간 복잡도: O(log n) 공간 복잡도: O(1)

문제 11: Median of Two Sorted Arrays (LeetCode 4) - 고난도

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
    # nums1이 더 짧은 배열이 되도록 보장
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    half_len = (m + n + 1) // 2

    left, right = 0, m

    while left <= right:
        i = (left + right) // 2  # nums1의 파티션
        j = half_len - i          # nums2의 파티션

        # i가 너무 작으면 오른쪽으로
        if i < m and nums1[i] < nums2[j - 1]:
            left = i + 1
        # i가 너무 크면 왼쪽으로
        elif i > 0 and nums1[i - 1] > nums2[j]:
            right = i - 1
        else:
            # 올바른 파티션 찾음
            if i == 0:
                max_left = nums2[j - 1]
            elif j == 0:
                max_left = nums1[i - 1]
            else:
                max_left = max(nums1[i - 1], nums2[j - 1])

            if (m + n) % 2 == 1:
                return float(max_left)

            if i == m:
                min_right = nums2[j]
            elif j == n:
                min_right = nums1[i]
            else:
                min_right = min(nums1[i], nums2[j])

            return (max_left + min_right) / 2.0

# 예시
# Input: nums1 = [1,3], nums2 = [2]
# Output: 2.0

시간 복잡도: O(log(min(m, n))) 공간 복잡도: O(1)

문제 12: Search a 2D Matrix (LeetCode 74)

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1

    while left <= right:
        mid = left + (right - left) // 2
        # 1D 인덱스를 2D 좌표로 변환
        mid_val = matrix[mid // cols][mid % cols]

        if mid_val == target:
            return True
        elif mid_val < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

# 예시
# Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# Output: True

시간 복잡도: O(log(m*n)) 공간 복잡도: O(1)

4. Prefix Sum & Hash Map 패턴

개념

Prefix Sum은 누적합을 미리 계산해 구간 합 쿼리를 O(1)에 처리합니다. Hash Map과 결합하면 특정 조건을 만족하는 구간을 효율적으로 찾을 수 있습니다.

문제 13: Subarray Sum Equals K (LeetCode 560)

합이 k인 연속 부분 배열의 개수를 구하라.

from collections import defaultdict

def subarraySum(nums: list[int], k: int) -> int:
    # prefix_sum_count[s] = prefix sum이 s인 경우의 수
    prefix_sum_count = defaultdict(int)
    prefix_sum_count[0] = 1  # 빈 배열의 prefix sum = 0

    current_sum = 0
    count = 0

    for num in nums:
        current_sum += num
        # current_sum - k가 이전에 나온 prefix sum이면 해당 구간의 합 = k
        count += prefix_sum_count[current_sum - k]
        prefix_sum_count[current_sum] += 1

    return count

# 예시
# Input: nums = [1,1,1], k = 2
# Output: 2

시간 복잡도: O(n) 공간 복잡도: O(n)

문제 14: Longest Consecutive Sequence (LeetCode 128)

정렬되지 않은 배열에서 가장 긴 연속 수열의 길이를 구하라 (O(n) 요구).

def longestConsecutive(nums: list[int]) -> int:
    num_set = set(nums)
    max_length = 0

    for num in num_set:
        # 수열의 시작점인 경우만 처리 (num-1이 없는 경우)
        if num - 1 not in num_set:
            current = num
            length = 1

            while current + 1 in num_set:
                current += 1
                length += 1

            max_length = max(max_length, length)

    return max_length

# 예시
# Input: nums = [100,4,200,1,3,2]
# Output: 4 ([1,2,3,4])

시간 복잡도: O(n) - 각 원소는 최대 두 번 방문 공간 복잡도: O(n)

문제 15: Group Anagrams (LeetCode 49)

문자열 배열을 애너그램끼리 묶어라.

from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    anagram_map = defaultdict(list)

    for s in strs:
        # 정렬된 문자열을 키로 사용
        key = tuple(sorted(s))
        anagram_map[key].append(s)

    return list(anagram_map.values())

# 카운터를 키로 사용하는 최적화 버전
def groupAnagramsOptimized(strs: list[str]) -> list[list[str]]:
    anagram_map = defaultdict(list)

    for s in strs:
        # 26개 알파벳 카운트를 키로 사용
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        anagram_map[tuple(count)].append(s)

    return list(anagram_map.values())

# 예시
# Input: strs = ["eat","tea","tan","ate","nat","bat"]
# Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

시간 복잡도: O(n _ k) - n은 문자열 수, k는 최대 문자열 길이 공간 복잡도: O(n _ k)

문제 16: Top K Frequent Elements (LeetCode 347)

from collections import Counter
import heapq

def topKFrequent(nums: list[int], k: int) -> list[int]:
    # 방법 1: 힙 사용 O(n log k)
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

def topKFrequentBucketSort(nums: list[int], k: int) -> list[int]:
    # 방법 2: 버킷 정렬 O(n)
    count = Counter(nums)

    # 빈도를 인덱스로 사용하는 버킷
    bucket = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        bucket[freq].append(num)

    result = []
    for freq in range(len(bucket) - 1, 0, -1):
        for num in bucket[freq]:
            result.append(num)
            if len(result) == k:
                return result

    return result

# 예시
# Input: nums = [1,1,1,2,2,3], k = 2
# Output: [1,2]

시간 복잡도: O(n) with Bucket Sort 공간 복잡도: O(n)

5. FAANG 기업별 배열/문자열 출제 경향

Google

Google 인터뷰는 Arrays와 String Manipulation에 집중합니다.

자주 출제: Two Sum 변형, 문자열 파싱, 2D 배열 탐색
핵심 스킬: 엣지 케이스 처리, 코드 명확성
예시 문제: Longest Substring with At Most K Distinct Characters, Minimum Number of Arrows to Burst Balloons

Meta (Facebook)

Meta는 Sliding Window와 Two Pointer 패턴을 선호합니다.

자주 출제: 3Sum, Valid Palindrome II, Move Zeroes
핵심 스킬: 최적화 이유 설명, 코드 간결성
예시 문제: Subarray Product Less Than K, Permutation in String

Amazon

Amazon은 Hash Table과 Sorting 기반 문제를 선호합니다.

자주 출제: Two Sum, Group Anagrams, Top K Frequent
핵심 스킬: 실용적인 해결책, LP(리더십 원칙) 연결
예시 문제: K Closest Points to Origin, Sort Colors

Microsoft

Microsoft는 Binary Search 변형과 배열 조작 문제를 자주 냅니다.

자주 출제: Find Peak Element, Search a 2D Matrix
핵심 스킬: 엣지 케이스, 버그 없는 코드
예시 문제: Spiral Matrix, Rotate Image

6. 인터뷰 실전 팁

문제 접근 프레임워크 (45분 기준)

1단계 - Clarify (5분)

면접관에게 반드시 확인할 사항들:

입력 범위와 타입 (음수 가능? 중복 있음?)
출력 형식 (인덱스? 값? 개수?)
엣지 케이스 (빈 배열, 단일 원소, 모두 같은 값)
최적화 목표 (시간 vs 공간)

2단계 - Brute Force (5분)

먼저 O(n^2) 또는 O(n^3) 브루트 포스를 설명합니다. 이것이 베이스라인이 됩니다.

3단계 - Optimize (10분)

패턴 인식: Two Pointers? Sliding Window? Hash Map? 면접관과 트레이드오프를 논의합니다.

4단계 - Code (15분)

깔끔하게 코딩합니다. 변수명은 명확하게, 주석은 핵심만:

def solve(nums, target):
    # 투 포인터 초기화
    left, right = 0, len(nums) - 1

    while left < right:
        # ... 로직
        pass

5단계 - Test (10분)

직접 테스트 케이스를 만들어 검증합니다:

정상 케이스
엣지 케이스 (빈 배열, 길이 1)
최악의 경우

엣지 케이스 체크리스트

배열/문자열 문제에서 반드시 확인:

빈 입력 ([], "")
단일 원소 ([5], "a")
모든 원소가 같은 값 ([3,3,3,3])
이미 정렬된 경우
역순 정렬된 경우
오버플로우 가능성 (int 범위 초과)
음수 포함 여부

시간 분배 전략

단계	시간	핵심 포인트
Clarify	5분	면접관에게 질문하며 요구사항 확인
Brute Force	5분	단순한 해법 먼저 제시
Optimize	10분	패턴 파악, 복잡도 개선
Coding	15분	깔끔하고 버그 없이
Testing	10분	직접 트레이스, 엣지 케이스

7. 연습 문제 퀴즈

퀴즈 1: Two Pointers로 정렬된 배열에서 중복 제거하기

정렬된 배열 nums = [0,0,1,1,1,2,2,3,3,4]에서 in-place로 중복을 제거하고 고유 원소의 수를 반환하라. 추가 공간은 O(1)만 사용 가능.

정답: 5 (배열은 [0,1,2,3,4,...])

설명: Two Pointers를 사용합니다. 느린 포인터(slow)는 다음에 쓸 위치를, 빠른 포인터(fast)는 탐색 위치를 가리킵니다. nums[fast] != nums[slow]이면 slow를 증가시키고 값을 복사합니다.

def removeDuplicates(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

퀴즈 2: Sliding Window로 최대 연속 1의 개수 구하기

이진 배열 nums = [1,1,0,0,1,1,1,0,1]에서 최대 k=1개의 0을 1로 바꿀 수 있을 때 가장 긴 연속 1의 부분 배열 길이를 구하라.

정답: 6

설명: Variable Sliding Window를 사용합니다. 윈도우 내 0의 개수가 k를 초과하면 왼쪽 포인터를 이동합니다.

def longestOnes(nums, k):
    left = 0
    zeros = 0
    max_len = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

퀴즈 3: Binary Search 응용 - 경계값 찾기

정렬된 배열 nums = [5,7,7,8,8,10]에서 target=8의 시작 인덱스와 끝 인덱스를 구하라.

정답: [3, 4]

설명: Binary Search를 두 번 실행합니다. 첫 번째는 가장 왼쪽 인덱스(leftmost), 두 번째는 가장 오른쪽 인덱스(rightmost)를 찾습니다.

def searchRange(nums, target):
    def findLeft(nums, target):
        left, right = 0, len(nums) - 1
        idx = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                idx = mid
                right = mid - 1  # 왼쪽으로 계속 탐색
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return idx

    def findRight(nums, target):
        left, right = 0, len(nums) - 1
        idx = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                idx = mid
                left = mid + 1  # 오른쪽으로 계속 탐색
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return idx

    return [findLeft(nums, target), findRight(nums, target)]

퀴즈 4: Prefix Sum으로 짝수 길이 구간의 합이 같은 경우 세기

배열 [1, -1, 1, -1, 1]에서 합이 0인 연속 부분 배열의 개수는?

정답: 4

설명: Prefix Sum + HashMap을 사용합니다. prefix sum이 같은 경우가 m번 나타나면 C(m,2)개의 구간이 합이 0입니다. prefix_sum_count를 이용해 count += prefix_sum_count[current_sum]으로 계산합니다.

from collections import defaultdict
def subarraySum(nums, k=0):
    prefix_sum_count = defaultdict(int)
    prefix_sum_count[0] = 1
    current_sum = 0
    count = 0
    for num in nums:
        current_sum += num
        count += prefix_sum_count[current_sum - k]
        prefix_sum_count[current_sum] += 1
    return count
# 결과: 4

퀴즈 5: 종합 문제 - Product of Array Except Self

배열 nums = [1,2,3,4]에서 각 위치에 대해 자기 자신을 제외한 나머지 원소의 곱을 구하라. 나눗셈 사용 금지, O(n) 시간, O(1) 추가 공간.

정답: [24, 12, 8, 6]

설명: 왼쪽 누적곱(prefix product)과 오른쪽 누적곱(suffix product)을 활용합니다. 출력 배열 자체를 재활용해 공간을 절약합니다.

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n

    # 왼쪽 누적곱
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # 오른쪽 누적곱을 곱하기
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

마무리

배열과 문자열 문제는 FAANG 인터뷰의 핵심입니다. 이 글에서 다룬 패턴들을 완전히 내재화하면 대부분의 문제를 빠르게 인식하고 최적 해법으로 접근할 수 있습니다.

다음 학습 단계:

LeetCode에서 각 패턴별 문제 20개씩 풀기
시간을 재며 45분 안에 해결하는 연습
코드 리뷰: 다른 사람의 풀이와 비교
면접관 역할로 직접 문제 출제해보기

다음 편에서는 트리와 그래프 패턴을 다룹니다.