리트코드 1218

문제 설명

주어진 문자열에서 difference 만큼 차이가 나게끔 하는 수열의 최대 길이를 구해야 하는 문제다.

예)
arr = [1, 2, 3, 4] difference = 1
최대 길이: 4

접근 방식

• 등차수열의 경우 i번째 수열에 해당하는 수가 i-1번째 수를 포함하게 되고, i-1번째 수는 i-2번째 수를 포함하게 된다.
• 예) 1 3 5 7 9의 수열에서 3은 1을 포함, 5는 3을 포함, 7은 5를 포함, 9는 7을 포함한다.
• 1은 아무것도 포함하지 않기 때문에 subsequence로 1을 갖게 되며, 3은 1을 포함하여 2개를 갖는다.

작성한 코드

class Solution:
    def longestSubsequence(arr, difference):
        num_dict = {}

        for num in arr:
            if num - difference in num_dict:
                num_dict[num] = num_dict[num-difference] + 1
            else:
                num_dict[num] = 1

        return (max(num_dict.values()))

딕셔너리를 이용해 간단하게 해결할 수 있지만, 아이디어 생각이 중요했던 문제다.