Find the Maximum Number of Elements in Subset

문제 번호, 이름: 3020. Find the Maximum Number of Elements in Subset

문제 링크: https://leetcode.com/problems/find-the-maximum-number-of-elements-in-subset/description/

날짜: 2024/05/26

상태: 완료

 

이 문제를 고른 이유

리트코드 랜덤픽

문제 보고 처음 든 생각

무슨 미디엄 문제에 힌트가 4개나 주렁주렁 달려있지..?

 

처음엔 머리가 하얗게 아무 생각도 안 들었지만..

nums.length <= 10^5 니까 충분히 작아서

number들을 hash table (dict를 쓰겠단 뜻)에 담아서 count값을 저장하면 될 것 같다

본인의 count가 2개 이상이고, 본인의 제곱수가 hash table에 있다면 본인의 제곱수를 타고타고 올라가서 조건이 만족 안되는 때까지 올라가기?

풀이 v1

• 소요 시간 13분

from collections import Counter

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        num_counter = Counter(nums)
        num_set = set(nums)
        visited_flag = {num: False for num in num_set}
        answer = -1

        for num in num_set:
            if visited_flag[num]:
                continue
            answer_candidate = 1
            visited_flag[num] = True
            while num_counter[num] >= 2 and num * num in num_set:
                num = num * num
                visited_flag[num] = True
                answer_candidate += 2
            answer = max(answer, answer_candidate)

        return answer

 

는 틀렸다

[1,1] TC에서 무한루프로 터졌다

풀이 v2

• 소요 시간 추가8분

from collections import Counter

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        num_counter = Counter(nums)
        num_set = set(nums)
        visited_flag = {num: False for num in num_set}
        answer = -1
        
        if 1 in num_set:
            answer = max(answer, num_counter[1] if num_counter[1] % 2 == 1 else num_counter[1] - 1)
            visited_flag[1] = True

        for num in num_set:
            if visited_flag[num]:
                continue
            answer_candidate = 1
            visited_flag[num] = True
            while num_counter[num] >= 2 and num * num in num_set:
                num = num * num
                visited_flag[num] = True
                answer_candidate += 2
            answer = max(answer, answer_candidate)

        return answer

 

1을 처리할 수 있는 범용적인 방법을 생각해 봤는데, 1만 따로 처리하는 것보다 효율적인 방법을 못 찾아서 결국 1만 처음에 따로 처리해 주었다.

다른 사람의 풀이는 어떨까

제일 뷰 수 많은 풀이를 봤는데 완벽히 나랑 같은 생각으로 풀었네;; 다들 1을 따로 처리해 준 것 같다

 

이 문제를 풀고 얻은 것

• 공부 열심히 해야겠다는 생각

메모

• 풀이를 생각해 볼 때 시간복잡도와 공간복잡도도 구체적인 식으로 떠올려보는 습관을 들이면 어떨까. 머릿속에 되겠다 안되겠다가 느낌적으로 떠오르긴 하는데.. 남에게 설명할 때에는 그렇게 말할 순 없으니까