[LeetCode] 2501. Longest Square Streak in an Array

https://leetcode.com/problems/longest-square-streak-in-an-array/description/?envType=daily-question&envId=2024-10-28

leetcode - Longest Square Streak in an Array

문제 유형: 해시, 집합, 이진 탐색, 다이나믹 프로그래밍

문제 난이도: Medium

 

문제

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.

 

정수 배열 nums를 받는다.

다음 조건을 만족하는 서브시퀀스는 square streak이라 할 수 있다.

• 길이가 최소 2 이상
• 정렬하고 나면, 첫 번째 원소를 제외하고 모든 원소는 이전 원소의 제곱이어야 한다.

최고 길이를 구하고, 없으면 -1을 반환하시오.

서브시퀀스는 배열에서 요소 몇 개를 뽑아서 만들 수 있습니다.(순서, 개수 상관없음)

 

풀이

dp + 이진탐색 풀이:

우선, 배열을 정렬하고 중복값을 없애준다.

그리고 dp[i] = nums[i]를 마지막으로 넣은 square streak의 길이로 정했다.

그리고, 배열을 순회하면서, 이진탐색을 이용해서 nums[i]의 제곱근이 있다면, 그 제곱근이 있는 인덱스를 j라 했을 때, dp[i] = dp[j] + 1이 된다.

 

최종적으로, dp에서 가장 큰 값이 2 이상이면 그 값을 반환하고, 아니면 -1을 반환한다.

 

bitset을 이용한 풀이: bitset말고도 set, unordered_map으로도 가능하다.

각 요소들을 1로 bitset에 저장한다. 이러면 그 수들이 존재한다는 의미이다.

각 수들을 순차적으로 반복하면서, 제곱수가 존재함을 확인하면, 계속 스트릭을 늘려나간다. 

만약 스트릭이 5라면, 힌트에 최대 스트릭 길이가 5라 되어있어서, 순회를 관두고 바로 5를 반환하면 된다. 아니면 그냥 최대값을 갱신하면 된다.

 

최종적으로, 가장 긴 스트릭이 2 이상이면 그 값을 반환하고, 아니면 -1을 반환한다.

 

코드

C++

 

dp + 이진탐색 풀이

class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        int n = nums.size();
        vector<int> dp(n, 1);


        int maxLen = 1;
        for(int i = 0; i < n; ++i) {
            auto root = lower_bound(nums.begin(), nums.end(), (int)sqrt(nums[i])) - nums.begin();
            if((long long)nums[root] * nums[root] == nums[i]) {
                dp[i] = dp[root] + 1;
                maxLen = max(maxLen, dp[i]);
            }
        }

        return maxLen == 1? -1 : maxLen;
    }
};

 

bitset을 이용한 풀이

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

const long long N = 100001;

class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        bitset<N> hasX=0;
        for(int x : nums) hasX[x] = 1;

        int maxStreak = 0;
        for(long long x : nums) {
            int streak = 1;
            for(long long z = x*x; z < N; z *= z) {
                if(hasX[z]) streak++;
                else break;
            }
            maxStreak = max(maxStreak, streak);
            if(maxStreak == 5) break;
        }

        return maxStreak < 2? -1 : maxStreak;
    }
};