Leetcode 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.

• 2 이상의 양의 정수로 이루어진 배열이 주어진다.
• 여기서 숫자들을 빼내어 배열을 새로 만들때, 이 배열을 정렬하면 [2, 4, 16] 과 같이 이전 수가 다음 수의 제곱근이 되게 하면
  • sqaure streak 이라고 부른다.
• 가장 큰 square streak의 길이를 리턴하시오.

예시

[4,3,6,16,8,2]

• [4, 2, 16] 을 정렬하면 [2, 4, 16]으로 square streak 이다.
• 3 이 리턴된다.

제한

• 2 <= nums.length <= 10^5
• 2 <= nums[i] <= 10^5

배열의 길이로 인해 O(N^2) 부터 시간이 부족하다.

풀이

• 일단 등장하는 모든 숫자들을 set으로 정리해 등장 여부를 확인하기 쉽게 한다.
• 이후 자기 자신으로부터 시작하는 square streak을 구하고, 그 길이를 구해 추가한다.
• 자기 자신으로부터 구하다가 이미 이전에 계산한 square streak 길이가 있으면 그걸 그대로 사용한다.

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        # 숫자 등장 확인용
        numbers = set(nums)

        # 스퀘어 스트릭 저장용
        check = defaultdict(int)
        ans = 0

        for num in nums:
            # 이미 검사한적 있는 숫자는 제외한다.
            if num in check:
                continue

            cnt = 1
            original = num

            while num <= 10 ** 5:
                # 스퀘어 스트릭을 검사한적 있으면 그냥 바로 사용한다.
                if num * num in check:
                    cnt += check[num * num]
                    break
                # 검사한적 없으면서 존재하는 숫자면 카운팅한다.
                elif num * num in numbers:
                    cnt += 1
                # 없으면 끝!
                else:
                    break
                num = num ** 2
            # 스퀘어 스트릭 저장
            check[original] = cnt
            # 최댓값 탐지
            ans = max(ans, cnt)

        return ans if ans != 1 else -1

소감

• 이제부터 Debug 의 사용을 최소한으로 줄이고 코드를 풀 예정이다.
• Contest, CodeTest 에서는 Debug의 사용이 제한되거나 불가능 한 경우가 많기 때문
• 이 외에도 제출또한 신중하게 할 예정