2024 10 28 2501. Longest Square Streak in an Array

문제

You are given an integer array nums. A subsequence of nums is called a square streak if:

The length of the subsequence is at least 2, and
after sorting the subsequence, each element (except the first element) is the square of the previous number.
Return the length of the longest square streak in nums, or return -1 if there is no square streak.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

요약

가장 강 긴 연속된 제곱 집합을 찾는 문제

풀이

처음에는 LMS ( 가장 긴 부분 집합)인가라고 생각 했지만 생각해보면 어떤수의 제곱이 되는 수를 찾는 것이기에 1대1 대응이라 한 수에서 그 제곱수가 존제하는지 판단하고 count를 해주면 되는 것이었다. (dp)

 

숫자가 최대 10_0000이라 316이하의 숫자만 제곱을 생각해주면 된다.

 

이때 조심해야 할 것이

중복된 수가 있다.

 

이는 visited 를 한번 계산한 숫자는 방문처리를 해주었다.

또한 초기 numIdx에 제곱한 숫자의 idx (nums 배열에서 해당 숫자의 위치)를 저장하는 곳에서 처음 나타났을 때만 그 숫자의 idx를 저장해주어 다른 같은 수는 무시하였다.

코드

import java.util.*;

class Solution {
    public int longestSquareStreak(int[] nums) {
        int[] count = new int[nums.length];
        boolean[] exists = new boolean[10_0001];
        boolean[] visited = new boolean[10_0001];
        int[] numIdx = new int[10_0001];
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i ++) {
            exists[nums[i]] = true;
            numIdx[nums[i]] = numIdx[nums[i]] == 0 ? i : numIdx[nums[i]];
            count[i] = 1;
        }
        // 316
        int max = 1;
        int root = 0;
        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] > 316 || visited[nums[i]]) {
                continue;
            }
            visited[nums[i]] = true;
            int square = nums[i] * nums[i];
            if (exists[square]) {
                int next = numIdx[square];
                count[next] += count[i];
                max = Math.max(count[next], max);
            }
        }
        if (max == 1) {
            return -1;
        }
        return max;
    }
}

풀이 시간

15분

체감 난이도

easy