2501. Longest Square Streak in an Array

Problem : https://leetcode.com/problems/longest-square-streak-in-an-array

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:04:39

 

---

 

문제 설명

 

정수 배열 nums가 주어질 때, nums의 부분 수열은 다음을 만족할 때 연속 제곱이라고 부른다

• 부분 수열의 길이가 최소한 2이다.
• 부분 수열을 정렬한 후, 첫 번째 원소를 제외한 나머지 원소들은 이전 원소의 제곱수이다.

nums의 연속 제곱의 최장 길이를 반환하라. 만약 그러한 연속 제곱이 없다면 -1를 반환하라.

부분 수열은 남은 원소의 순서를 바꾸지 않고 일부 원소를 제거함으로써 얻어지는 배열을 의미한다.

---

 

풀이

 

부분 수열의 정의는 약간의 함정이 있다. square streak은 순서의 상관을 두지 않으므로(정렬한 후를 규정하고 있다) 우리는 순서와 상관 없이 제곱을 만족하는 숫자쌍을 찾는다고 생각하자.

 

맨 처음의 풀이(제일 빨리 풀었던)는 정렬에 주목했다.

• 오름차순으로 정렬을 수행한다. 시간복잡도는 O(NlogN)이며, 그 결과로 수열의 뒤쪽 원소는 앞의 원소보다 크거나 같음이 보장된다(단조 증가)
• 이제 순서대로 수열을 방문할 것이다. map 형태의 자료구조(파이썬에서는 딕셔너리)를 이용해 DP를 수행한다고 생각하자.
  • map의 key는 연속 제곱이 이어지는 다음 숫자를 의미하며, value는 연속 제곱의 길이를 의미한다.
  • 예를 들어, (key, value) = (16, 2)라고 두자. 그렇다면 이 연속 제곱은 (2, 4)형태로 구성되어 있는 셈이다(4 * 4 = 16이므로 다음 수로 16을 요구, 현재 연속 제곱의 길이는 2)
  • 만약 현재 숫자 n이 map의 key에 존재한다면, 연속 제곱의 길이는 더 길어질 수 있다. 즉 visited[n ** 2] = max(visited[n ** 2], visited[n] + 1)이 된다.
  • 그렇지 않다면, 이 숫자부터 연속 제곱이 시작될 가능성을 고려하여 저장한다. 즉 visited[n ** 2] = 1이 된다.
• 모든 순회를 마친 후, map의 value중 가장 큰 값을 반환하면 된다.

 

 

풀이 코드(정렬 + DP)

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        nums.sort()
        visited = defaultdict(int)
        result = 0

        for n in nums :
            if n not in visited :
                visited[n ** 2] = 1
            else :
                visited[n ** 2] = max(visited[n ** 2], visited[n] + 1)
            result = max(result, visited[n ** 2])
            
        return result if result > 1 else -1

 

이 방식의 유일한 단점은 초기 정렬이 O(NlogN)이 소요된다는 점이다.

 

위 풀이에서 핵심을 되짚어 보면, 현재 확인하는 숫자의 제곱수가 어떤 자료구조 안에 존재하는지 검사한다는 점을 꼽아볼 수 있다. 즉 이에 주목해서 좀 더 효율적인 풀이를 생각해보자.

 

제곱수는 생각보다 빨리 커진다. 2부터 시작하는 연속 제곱을 생각해 보면, length = 4일때 마지막 수는 2 ^ (2 ^ 4) = 2 ^ 16 = 65536이 된다. 조건으로 주어진 최대 숫자가 10 ^ 5 이하이므로, 연속 제곱이 될 수 있는 정답은 2, 3, 4 중 하나이다.

 

그럼 아예 nums의 원소들을 나열해서 연속 제곱을 만들지 말고, 연속 제곱을 만들며 nums의 원소를 검사하면 어떨까?

 

• nums를 map(파이썬에선 set)형태로 변환하는 데는 O(N)의 시간복잡도가 소모될 것이다. 
• nums를 순회하며, 각 nums의 원소 n에 대해 n에서부터 시작되는 연속 제곱 배열을 찾는다고 가정한다.
  • n ^ 2이 nums에 존재하는 지 검사하는 데는 O(1)이 소요된다(map으로 변환했으므로)
  • 이제 nums에 존재하지 않는 n ^ 2가 나올 때까지, n을 제곱하고 반복해서 적용할 것이다.
  • 이 반복은 상수 시간복잡도로 보아도 될 정도로 빠르게 소요된다. 엄밀하게 따져보고 싶다면 다음 접은글을 확인해보자.
  • n이 어떤 연속 제곱 숫자의 마지막 값이라면,  길이 탐색에는 엄밀하게 O(loglog(n)) 시간복잡도가 소요된다. 뒤에 오는 제곱수는 앞선 제곱수의 제곱배의 형태로 매우 빠르게 늘어나므로 생기는 현상이다.
    
    이를테면 log의 밑이 2일때, O(loglog65536) = 4이다.
    
    즉 한 원소에 대한 시간복잡도는 O(loglog(n))이다. n의 최대 크기가 10^5이므로 상수 시간복잡도라고 보아도 된다.
• 모든 순회가 끝났을 때, 자연스럽게 최대 연속 제곱 길이를 구할 수 있다.

 

풀이 코드(개선된 버전)

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        nums = set(nums)
        MAX = 10 ** 5
        result = 0

        for n in nums :
            n *= n
            ret = 1
            while n in nums :
                ret += 1
                n *= n
            result = max(result, ret)
        
        return result if result > 1 else -1