[leetcode] 446. Arithmetic Slices II - Subsequence

문제 : https://leetcode.com/problems/arithmetic-slices-ii-subsequence/

---

정수 배열 nums가 주어지면 모든 arithmetic subsequences 의 수를 구하라.

시퀀스들의 숫자가 3개 이상이고 연속되는 두 요소의 차이가 동일한 경우 arithmetic subsequences라 한다.

---

i:j->(j-i)가 차이이고 i, j를 포함하는 subsequences 수 (i>j)

4:2->1 [4,2]

6:2->1  [6,2]
6:4->2  [6,4,2]
	[6,4]

8:2->1  [8,2]
8:4->1  [8,4]
8:6->3  [8,6,4,2]
	[8,6,4]
	[8,6]

10:2->1 [10,2]
10:4->1 [10,4]
10:6->2 [10,6,2]
	[10,6]
10:8->4 [10,8,6,4,2]
	[10,8,6,4]
	[10,8,6]
	[10,8]

를 구해보면 위와 같다.

 

문제에서 조건을 보면 subsequence의 원소 수가 3개 이상이어야 한다. 

i, j를 포함해야 하므로 모든 subsequence들은 2개 이상의 수를 가지므로 한 개를 제외하고는 모두 3개 이상의 원소를 가진다. 따라서 정답엔 각 수들에 -1한 값들을 더해야 한다. 

 

dp[i][diff] = (j-i)가 차이이고 i, j를 포함하는 subsequences 수.

 = dp[0~j][diff] + 1 (j < i)

dp[i][diff] = (j-i)가 차이이고 i, j를 포함하는 subsequences 수.
	= dp[0~j][diff] + 1 (j < i)

dp 점화식은 위와 같다.

 

시간복잡도는 O(N^2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/446.%20Arithmetic%20Slices%20II%20-%20Subsequence.cpp

---

vector<unordered_map<long, int>> dp(n); 

// #1
int cnt = dp[j][diff];
// #2
int cnt = dp[j].count(diff) ? dp[j][diff] : 0;

코드 구현시 unordered_map를 key값으로 조회할 때 #1 과 같은 방법으로 접근하게 짜면 TLE가 발생한다.

#2 로 작성하면 Accepted 를 받을 수 있다.

unordered_map []에 대한 reference를 찾아보았다.

[]를 사용하여 접근하게 되면 key와 매칭되는게 없더라도 map에 element를 하나 추가시켜 컨테이너 사이즈가 증가하게 된다.

따라서, unordered_map에 count가 0인 element들도 쌓이게 되어 크기가 커지게 되고 key 값으로 접근할때도 시간이 증가하게 된다.

사실 알고 있던 부분인데 시간 얼마나 차이나겠어 하고 무시했던 부분이다.. 앞으로는 주의하자.