Leetcode 1218. Longest Arithmetic Subsequence of Given Difference

https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/description/

Longest Arithmetic Subsequence of Given Difference - LeetCode

문제

정수로 이루어진 배열 arr와 정수 difference가 주어진다. 이 때 부분집합을 만들어 인전합 엘레멘트들 간의 차가 difference와 같은 가장 긴 부분집합을 반환하여라

 

부분집합은 배열 arr로 부터 파생된 것이면서 중간의 엘레멘트는 생략할 수는 있지만 값을 변경하거나 순서를 변경하는 행위를 하지 않고 만들어진 배열을 말한다.

 

예를 들어 [1, 5, 7, 8, 5, 3, 4, 2, 1]의 배열이 존재한다면, [1,7,8,1]은 부분집합이지만, [5,1,5,2]는 부분집합이라고 할 수 없다 그 이유는 첫번째 1 이전에 5가 없고 두번째 1 이후에 숫자가 없기 때문이다.

 

코드

class Solution:

    def longestSubsequence(self, arr: list[int], difference: int) -> int:

        if difference == 0:

            return max([arr.count(x) for x in arr])

        # value : index, it represent where is the number.

        m = {}

        # represent how many equals difference

        mm = [0] * len(arr)

        diff = -1 * difference

        for k, v in enumerate(arr):

            m[v] = k

            if (v + diff) in m:

                mm[k] = mm[m[v+diff]] + 1

            else:

                mm[k] = 1

        # print(m)

        # print(mm)

        return max(mm)

---

DP 문제인듯 해서 굉장히 당황했으나 조금 생각해보니 풀 수 있을 것 같아 빠른 시간내에 문제를 풀 수 있었다. 코드에 대해서 간략하게 설명하면, 주석에 나와있는대로 m은 arr에서 등장하는 값이 어디 인덱스에 있는지에 대한 정보를 담고 있는 딕셔너리이고, mm은 arr와 일대일 대응되는 배열로서 이 값이 얼마만큼 연속할 수 있는지에 대한 정보를 담고 있는 배열이다.

 

예를 들어 [1,4,6,7]의 배열과 difference가 3이 존재한다면 있다면 [1,2,1,3]과 같이 mm이 결정되길 바랬다.

 

그리고 difference의 부호를 반대로하여 arr를 왼쪽에서부터 오른쪽으로 훑을수 있도록 부호를 조정하였다. (설명을 적으면서 다시 생각해보면 굳이 부호를 바꿀 필요는 없을 듯 하다)

 

그리고 나서 반복문을 돌면서 변수의 용도에 따라 m 딕셔너리에 밸류와 밸류의 인덱스 값을 넣고 나서 만약 m에 현재 인덱스가 가리키고 있는 값 + diff의 값이 존재한다면,  값 + diff의 인덱스를 m에 찾아 그 m에 해당하는 값에 + 1을 해주어 연속각 값의 연속 갯수를 카운트 하였다. 그리고 만약 값을 찾지 못한다면 그 수는 연속되지 않음을 뜻하는 것이기에 1을 넣어주어 O(n)으로 문제에서 원하는 값을 찾을 수 있었다.

 

그리고 제출을 했으나 차이가 0인 경우 내가 작성한 코드의 경우 최신의 값에 대한 인덱스만을 m에서 보유하고 있는 코드이기에 따로 분기를 설정하여 코드를 작성했다.