hyunkookim 님의 블로그

560. Subarray Sum Equals K 누적합 + 해시맵을 사용하는 대표적인 패턴 문제입니다.✅ 문제 요약배열 nums와 정수 k가 주어질 때,연속된 구간(subarray)의 합이 k가 되는 경우의 수를 구하라. from collections import defaultdictclass Solution: def subarraySum(self, nums: List[int], k: int) -> int: count = 0 # 정답: 합이 k인 서브어레이의 개수 prefixSum = 0 # 누적합 (0부터 현재 인덱스까지의 합) prefixCount = defaultdict(in..

724. Find Pivot Index 1) Prefix Sums 누적합 이용 풀이 방법class Solution: def pivotIndex(self, nums: List[int]) -> int: # 자신을 제외한 왼쪽 합 == 오른쪽 합이 되는 pivot index를 찾는 문제 total = 0 # 전체 합을 계산하기 위한 변수 PrefixSum = [] # 0번 인덱스부터의 누적합 배열 for n in nums: total += n # 현재까지의 누적합을 계산 PrefixSum.append(total) # 누적합을 배열..

304. Range Sum Query 2D - Immutable class NumMatrix: def __init__(self, matrix: List[List[int]]): self.matrix = matrix rows, cols = len(matrix), len(matrix[0]) # prefixSums[i][j]는 (0,0)부터 (i,j)까지의 누적합을 저장 self.prefixSums = [[0] * cols for _ in range(rows)] for r in range(rows): for c in range(cols): top = self.prefixSums[r-1][c] if ..

303. Range Sum Query - Immutable class NumArray: def __init__(self, nums: List[int]): self.nums = nums self.area = [0]*len(nums) self.area[0] = nums[0] # 첫 원소는 그대로 할당 for i in range(1, len(nums)): self.area[i] = self.area[i - 1] + nums[i] # 누적합 계산 def sumRange(self, left: int, right: int) -> int: if left == 0: return self.area[righ..

238. Product of Array Except Self  문제 풀이이 문제는 주어진 배열 nums에서, 각 요소를 제외한 나머지 요소들의 곱을 계산하여 결과 배열을 반환하는 문제입니다. 나눗셈 없이, 시간 복잡도 O(n) 로 해결해야 합니다.문제 조건각 answer[i] 는 배열 nums의 i 번째 요소를 제외한 나머지 요소들의 곱입니다.나눗셈 사용 금지: 단순히 배열 전체 곱을 구한 뒤 각 요소로 나누는 방식은 사용할 수 없습니다.시간 복잡도는 O(n), 공간 복잡도는 O(1) 추가 공간(결과 배열은 제외).풀이 방법1. 아이디어배열의 곱을 효율적으로 계산하려면 다음과 같은 접근법을 사용할 수 있습니다:왼쪽 누적 곱 (prefix product): 각 요소 iii에서, 왼쪽에 있는 모든 요소들의 ..