[leetecode 오늘의 문제] 446. Arithmetic Slices II - Subsequence
알고리즘 문제를 풀다보면 영어로 수학 용어를 알 필요를 종종 느끼게 된다. Arithmetic subsequences 는 등차수열이다.
이 문제에서는 nums 라는 배열에서 부분 등차 수열의 개수를 찾아야 하는데, 등차 수열은
- 적어도 세 개의 요소를 가지고 있으며,
- 연속하는 두 요소 사이의 차이가 동일하다는
것을 의미한다.
각 요소에 대한 defaultdict 초기화
배열의 각 요소에 대해, 특정 공차로 끝나는 부분 수열의 개수를 저장할 defaultdict을 생성한다.
subsequences = [defaultdict(int) for _ in nums]
total_count = 0
* defaultdict 를 사용하는 이유 - 존재하지 않는 키 처리
이 문제를 풀 때에는 공차( diff = nums[i] - nums[j] )를 계속해서 업데이트 해야 한다. 이때 defaultdic(int) 는 키가 존재하지 않는다면 기본값 0으로 초기화 하는데, 이 덕분에 키의 존재 여부를 확인하지 않고도 개수를 0부터 셀 수 있어서 편리하다.
즉, defaultdict 를 사용하지 않는다면 키가 있는지를 확인하고 초기화하는 로직을 추가할 필요가 없어서 효율적이다.
순회
for i in range(len(nums)):
for j in range(i):공차 계산
diff = nums[i] - nums[j]
diff는 nums[i] - nums[j]다.
nums[j]의 defaultdict에 이 차이가 이미 존재한다면, nums[i]를 추가하여 해당 부분 수열을 확장할 수 있음을 의미한다.
개수 업데이트
count_at_j = subsequences[j][diff]
count_at_i = subsequences[i][diff]
subsequences[i][diff] = count_at_i + count_at_j + 1
각 쌍 (i, j)에 대해, diff에 대한 nums[i]의 맵의 개수를 업데이트한다.
이 개수는 nums[j]에서 동일한 diff로 끝나는 부분 수열의 수(있는 경우)와 새로 형성된 부분 수열 [nums[j], nums[i]]의 합이다.
부분 수열 개수 세기
total_count += count_at_j
nums[i]가 추가될 때 적어도 세 요소를 가진 유효한 등차 부분 수열의 수를 정확하게 반영하기 때문에 총 개수에 count_at_j를 추가한다.
count_at_i는 배열을 계속 처리하면서 추가적인 확장을 위한 잠재적인 부분 수열을 추적하는 데 사용한다.
- 부분 수열 확장
- (i, j) 쌍 (i > j)에서, nums[j]로 끝나는 기존 부분 수열을 nums[i]를 추가함으로써 확장
- 확장될 수 있는 부분 수열은 nums[i] - nums[j]와 같은 공차를 가진 수열
- 등차 부분 수열 계산
- 적어도 세 요소를 가진 부분 수열을 계산
- 따라서 (i, j) 쌍을 찾아 부분 수열을 확장할 수 있으면, 그 수열은 이미 적어도 두 요소(nums[j]에서 끝나는)를 가졌으며 이제 적어도 세 요소(nums[i]에서 끝나는)를 가질 것
- count_at_j
- count_at_j에 저장된 개수는 nums[i]를 추가함으로써 확장될 수 있는 nums[j]로 끝나는 부분 수열의 수
- 이러한 각각의 개수는 적어도 세 요소를 가진 새로운 유효한 등차 부분 수열
- count_at_i
- count_at_i는 특정 공차를 가진 nums[i]로 끝나는 모든 부분 수열(두 요소만 있는 수열 포함)
- (i, j) 쌍을 찾을 때마다 count_at_i를 증가시키므로, 이는 아직 유효하지 않은 부분 수열(즉, 적어도 세 요소가 없는)도 포함