문제 설명
https://leetcode.com/problems/arithmetic-slices/
arithmetic slice란 1,2,3,4 또는 -1, -3, -5 -7 처럼 같은 간격으로 3개 이상 이어진 숫자열을 의미한다. 일종의 Dynamic programming 문제인데, 규칙을 보면 아래와 같다.
1) 최대 arithmetic slice 길이가 3일때 ex. [1,2,3] 총 arithmetic slice의 길이는 [1,2,3] 으로 1개
2) 4일때 ex. [1,2,3,4] [1,2,3,4] [1,2,3] [2,3,4] 로 총 3개
3) 5일때 ex.[1,2,3,4,5] [1,2,3,4,5] [1,2,3,4] [2,3,4,5] [1,2,3] [2,3,4] [3,4,5] 총 6개
… 로 쭉 계산해보면 1, 3, 6, 10 과 같이 2, 3, 4, 5의 차이로 증가하는 것을 알 수 있다. 이를 토대로 점화식을 세워보면
An = An-1 + (n-2)
가 된다.
이를 토대로 코드를 구현하였다.
풀이
참고로 아래 코드는 정답 Pass 를 목적으로만 작성되어 깔끔하지는 않은 코드다. Runtime: 84 ms, faster than 12.79% of Python3 online submissions for Arithmetic Slices. Memory Usage: 14.7 MB, less than 11.28% of Python3 online submissions for Arithmetic Slices.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
# 최대 길이가 n이라고 하면 아래 공식이 성립
# An = An-1 + (n-2)
# 해당 값을 아래 해쉬맵에 저장
hash_map ={
}
def get_max_slice_len():
# 첫 원소의 차이를 계산하고 일단 길이 2로 시작
diff = nums[1] - nums[0]
leng = 2
result = 0
for i, val in enumerate(nums[1:-1],1):
# 차이가 같으면 길이를 증가시킴
if diff == nums[i+1] - nums[i]:
leng += 1
# 차이가 다른 지점이 나타나면 기존 길이값이 3이상인 경우에 대해서만 result에 더해줌
else:
diff = nums[i+1] - nums[i]
if leng >= 3:
result += hash_map[leng]
leng = 2
# 마지막 값에 대한 처리
if leng >= 3:
result += hash_map[leng]
return result
# 길이가 3 미만이면 0 리턴
if len(nums) < 3:
return 0
# 해쉬맵에 An = An-1 + (n-2) 계산하여 저장
ex_val = 1
hash_map[3] = 1
for i in range(4, len(nums)+1):
ex_val = ex_val + (i - 2)
hash_map[i] = ex_val
# 최대 arithmetic slice 갯수를 구함
max_slice_len = get_max_slice_len()
return max_slice_len