[leet code] 873. Length of Longest Fibonacci Subsequence (JAVA)

[leet code] 873. Length of Longest Fibonacci Subsequence

🗒️알고리즘 분류

#brute force #완전 탐색

✏️문제 설명

점점 증가하는 양수의 숫자들(오름차순)로만 이루어진 배열 arr 이 있다. 이 배열의 부분 수열 중에 피보나치 숫자들로만 이루어진 가장 긴 수열의 길이를 반환해라.
만약 없다면 0 을 반환해라.
제한조건:

• 3 <= arr.length <= 1000
• 1 <= arr[i] < arr[i + 1] <= 109

📌기억할 만한 포인트

처음에 이 문제를 봤을 때는 당황해서 어떻게 풀지 생각이 안났다. 하지만, 천천히 생각해보면 꽤나 간단한 문제이다.

배열 arr 의 최대 길이가 1000 이므로 완전 탐색(여기서는 O(N^2))으로 문제를 풀 수 있다.

• 처음에 배열의 수들을 모두 Set 에 넣어둔다.
• 배열에서 겹치지 않게 2개의 수를 선택한 후, 그들을 합치면서 Set 에 존재하는지 확인한다.
  • 존재한다면, 합한 수와 이전 수 중에 큰 수를 다시 합하면서 Set 에 존재하는지 확인한다.(이 과정을 Set 에 존재하지 않을 때 까지 반복한다.)
  • 존재 안한다면 최대 길이를 갱신하고, 다음 두 수를 선택한다.

📝풀이 코드(JAVA)

import java.util.*;

class Solution {
    
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;

        Set<Integer> set = new HashSet<>();
        for (int num : arr) {
            set.add(num);
        }
        
        int answer = 0;
        // 모든 가능한 두 수를 시작으로 시도
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int x = arr[i], y = arr[j];
                int length = 2;
                // Fibonacci-like 조건: x + y가 존재하면 시퀀스를 확장
                while (set.contains(x + y)) {
                    int z = x + y;
                    x = y;
                    y = z;
                    ++length;
                }
                if (length >= 3) {
                    answer = Math.max(answer, length);
                }
            }
        }

        return answer;
    }
}

⏰총 풀이시간

• 45분