[leetcode] 873. Length of Longest Fibonacci Subsequence

 

문제 링크

LeetCode - The World's Leading Online Programming Learning Platform

 

주어진 배열의 Subsequence 중 Fibonacci 한 배열의 최장 길이를 구하는 문제이다.

Fibonacci 라 하면, 3개의 수를 가지고 규칙이 성립되는 지 확인해야 하니까 어떻게 코드를 짜야할 지 막막할 수 있다.

(3개의 수라고 말한 이유는 a+b=c 가 성립되면, a,b,c 이 3개의 수가 피보나치 배열이라고 말할 수 있기 때문이다.)

 

---

 

Approach 1: Brute Force with Set

 

a 와 b 까지는 이중 loop 로 선택하면 되지만,

a+b = c 를 성립하는 c 를 빠르게 구하기 위해서 Set() 에 해당 수가 이미 있는 지 확인하는게 포인트이다.

그래서 c 가 Set() 에 존재한다면, a 와 b 를 Update 해준다. (a,b) -> (b, c)

 

from typing import List


class Solution(object):
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        S = set(arr)
        ans = 0
        for i in range(len(arr)): # 첫번째 수를 pick
            for j in range(i + 1, len(arr)): # 두번째 수를 pick
                a, b = arr[j], arr[i] + arr[j]
                length = 2
                while b in S: # 세번째 수가 Set 에 있는 지 확인하고, 있으면 Loop 로 이어나감
                    a, b = b, a + b
                    length += 1
                ans = max(ans, length)
        return ans if ans >= 3 else 0

 

---

 

Approach 2: Dynamic Programming

 

 

(원활한 이해를 돕기 위해, 위 그림에서 표현한 용어를 그대로 사용하겠다.)

"현재 요소" 와 "이전 요소" 를 이중 loop 로 먼저 선택하고, "더 이전 요소" 가 HashMap 에 존재하는지 확인한다.

단, 여기서 Brute Force 풀이에서 사용한 Set 이 아니라 HashMap 을 이용한 이유는 "더 이전 요소" 를 pick 할 때 "이전 요소" 보다 이전에 위치한 값을 pick 해야 하기 때문에 HashMap 을 이용하여 위치값(index) 도 저장하기 위해서이다.

(ex. [0,2, ...] 배열 예시를 생각해보면 바로 이해가 갈 것이다) 

 

from typing import List
from collections import defaultdict


class Solution(object):
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        valToIdx = {v: i for i, v in enumerate(arr)}  
        dp = defaultdict(int)  # dp[(이전요소,현재요소)] = 현재요소를 마지막으로 하는 배열의 longest length
        for i in range(2, len(arr)):  # 현재 요소를 pick
            for j in range(i):  # 이전 요소를 pick
                prevVal = arr[i] - arr[j]
                if prevVal in valToIdx and valToIdx[prevVal] < j: # 더 이전 요소를 pick
                    dp[(arr[j], arr[i])] = dp.get((prevVal, arr[j]), 2) + 1

        return max(dp.values()) if dp else 0