[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는 배열을 계속 처리하면서 추가적인 확장을 위한 잠재적인 부분 수열을 추적하는 데 사용한다.

 

1. 부분 수열 확장
   • (i, j) 쌍 (i > j)에서, nums[j]로 끝나는 기존 부분 수열을 nums[i]를 추가함으로써 확장
   • 확장될 수 있는 부분 수열은 nums[i] - nums[j]와 같은 공차를 가진 수열
2. 등차 부분 수열 계산
   • 적어도 세 요소를 가진 부분 수열을 계산
   • 따라서 (i, j) 쌍을 찾아 부분 수열을 확장할 수 있으면, 그 수열은 이미 적어도 두 요소(nums[j]에서 끝나는)를 가졌으며 이제 적어도 세 요소(nums[i]에서 끝나는)를 가질 것
3. count_at_j
   • count_at_j에 저장된 개수는 nums[i]를 추가함으로써 확장될 수 있는 nums[j]로 끝나는 부분 수열의 수
   • 이러한 각각의 개수는 적어도 세 요소를 가진 새로운 유효한 등차 부분 수열
4. count_at_i
   • count_at_i는 특정 공차를 가진 nums[i]로 끝나는 모든 부분 수열(두 요소만 있는 수열 포함)
   • (i, j) 쌍을 찾을 때마다 count_at_i를 증가시키므로, 이는 아직 유효하지 않은 부분 수열(즉, 적어도 세 요소가 없는)도 포함