[Alg] Daily LeetCoding Challenge 22.03.03: 413 Arithmetic Slices

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

입력 배열에서 arithmetic 부분배열을 출력하는 문제! arithmetic이 되기 위해서는 적어도 3개의 원소가 들어가야 하고, 연속되는 두 개의 원소의 차가 2여야 한다. nums가 [1, 2, 3, 4, 5] 라고 가정해보자. 만들 수 있는 arithmetic은 [1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 3, 4, 5] 로 총 6개가 된다. 여기서의 규칙은 먼저 [1, 2, 3]과 [2, 3, 4]가 만들어지면, [1, 2, 3, 4]도 만들 수 있다는 것이다. 더군다나 [3, 4, 5]까지 만들 수 있다면, [2, 3, 4, 5], [1, 2, 3, 4, 5]까지 만들 수 있다는 것이다.

차근히 생각해보자.

반복문을 돌다가 3을 탐색하는 경우에 3까지 연속되는 두 개의 원소의 차가 2라는 조건과 원소가 적어도 3개라는 조건을 만족한다면 1개의 arithmetic을 만들 수 있다.

4를 탐색하는 경우에도 연속되는 두 개의 원소의 차가 2라는 조건과 원소가 적어도 3개라는 조건을 만족한다면 1개의 arithmetic을 만들 수 있다. 그렇담 연속되는 두 개의 원소의 차가 2라는 조건과 원소가 4개라는 조건도 만족한다면 4를 만난 경우에 총 2개의 arithmetic을 만들 수 있다.

5를 탐색하는 경우에도 연속되는 두 개의 원소의 차가 2라는 조건과 원소가 적어도 3개라는 조건에서 1개, 연속되는 두 개의 원소의 차가 2라는 조건과 원소가 4개라는 조건에서 총 2개, 연속되는 두 개의 원소의 차가 2라는 조건과 원소가 5개라는 조건에서 총 3개를 카운팅할 수 있겠다. 

만약에 연속되는 두 개의 원소의 차가 2라는 조건이 만족되지 않는 경우를 만난다면 어떻게 될까? 예를 들어 [1, 5, 9, 13, 20, 29, 38, 46] 라는 배열이 있다고 해보자. 위에서 예를 든 것처럼 13을 탐색하는 순간에는 [1, 5, 9], [1, 5, 9, 13], [5, 9, 13] 총 3개의 arithmetic을 만들 수 있다. 하지만 20을 탐색하는 경우에는, [9, 13, 20]을 만들 수 없기 때문에 20에서 만들 수 있는 arithmetic은 0개가 된다. 29도 역시 마찬가지다. 38을 탐색하는 경우에는 [20, 29, 38]이라는 arithmetic 1개를 만들 수 있다. 하지만 이전에 29와 20에서 만든 arithemtic이 없기 때문에 연장해서 새로운 arithemic을 만들 수는 없다. 38은 1개 밖에 만들지 못한다. 46을 탐색하는 경우에는 조건을 만족하기 때문에 1개 만들 수 있으며, 38을 탐색했을 때 1개의 arithemic을 만들었기 때문에 그에 연장하여 총 2개를 만들 수 있다. 

따라서, 이전에 만들었던 값을 기억해야 되기 때문에 배열에 이전 값을 저장하고 현재 값을 그에 더해주기만 하면 된다. 위의 예처럼 조건을 만족하지 못하는 경우에는 0으로 두면 되기 때문에 따로 핸들링할 필요는 없다! 

 

슬라이딩 윈도우를 이용해서 푸는 방법도 있는데 오늘은 넘 졸려서 못하겠다. 담에 정리해서 올려야지~ ^-^ 허헣