[ leetcode ] 1218. Longest Arithmetic Subsequence of Given Difference

해당 문제는 숫자 배열과 diff가 주어졌을 때, arr의 subsequence 중에서 diff간격으로 이어지는 가장 긴 subsequence 길이를 반환하는 문제입니다. subsequence는 연속되지 않아도 됩니다.

특정 숫자로 시작하는 subsequence길이를 저장하는 것이 주요하여 map<int, int>자료 구조를 사용하여 특정 숫자로 끝나는 subsequence의 최대 길이를 저장해두었습니다.

 

subsequence는 diff를 더해가며 나오는 배열의 길이를 찾는 것이므로, i번째 숫자 - diff가 이미 map에 존재한다면 그 길이에 +1을 해서 i번째 숫자를 map에 저장해두고 반복해나가면 됩니다.

즉, arr[i] - diff가 map에 이미 존재한다면 arr[i] - diff까지의 길이 + 1을 arr[i]숫자에 저장해줍니다.

#include <map>
#define max(a,b)((a) > (b) ? (a) : (b))

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        map<int, int> index_list;
        int answer = 0;

        for (int i = 0; i < arr.size(); i++) {
            int temp = arr[i];
            if (index_list.find(temp - difference) != index_list.end())
                index_list[temp] = index_list[temp - difference] + 1;
            else 
                index_list[temp] = 1;
            answer = max(answer, index_list[temp]);
        }
        
        return answer;
    }
};