[LeetCode] 3020. Find the Maximum Number of Elements in Subset

https://leetcode.com/problems/find-the-maximum-number-of-elements-in-subset/description/?envType=daily-question&envId=2026-06-27

Find the Maximum Number of Elements in Subset - LeetCode

 

문제 정의

1. nums라는 양의 정수 배열이 주어진다.

2. 이때 부분집합을 골라서 배열했을때 팰린드롬 모양(대칭)이 되어야 한다.

3. x, x^2, x^4 *** x^4, x^2, x 이런식으로 나와야 한다.

 

 

문제 접근

결국 양쪽 대칭이 되어야 하기 때문에 map을 사용해서 nums 라는 배열중 원소의 개수를 하나씩 다 세줘야 한다. 그 이유는 제일 높은 대칭 탑을 이루기 위해서는 각 원소가 2개 이상씩 있어야 하며 마지막 가장 높은 원소는 1개 이상이 있어야 한다.

 

map을 사용해서 개수를 세준 후 map을 순환하여 하나를 잡고 어디까지 올라갈 수 있는지 확인하며 최대 개수를 업데이트 해주었다.

 

작성 코드(C++)

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        map<int, int> m;

        for(auto &iter : nums) m[iter]++;

        int result = 1;

        for(auto &iter : m) {
            long long val = iter.first;
            int count = iter.second;
            if(val == 1) continue;
            int len = 0;

            while(m.count(val) && m[val] >= 2) {
                len += 2;
                if(val > 1e9) {
                    val = -1;
                    break;
                }
                val = val * val;
            }

            len += (m.count(val)? 1 : -1);
            result = max(result, len);
        }

        if(m.count(1)) {
            int res = m[1];
            result = max(result, res % 2 == 1? res: res-1);
        }

        return result;
    }
};

 

 

작성코드(Java)

class Solution {
    public int maximumLength(int[] nums) {
        Map<Long, Integer> m = new HashMap<>();
        int result = 1;

        for(int a : nums) {
            m.put((long)a, m.getOrDefault((long)a, 0) + 1);
        }

        for(long key : m.keySet()) {
            long val = key;
            if(val == 1) continue;
            int count = m.get(key);
            int len = 0;

            while(m.containsKey(val) && m.get(val) >= 2) {
                len += 2;
                if(val >= Long.MAX_VALUE) {
                    val = -1;
                    break;
                }
                val = val * val;
            }

            result = Math.max(result, m.containsKey(val)? len+1 : len-1);
        }

        if(m.containsKey(1L)) {
            result = Math.max(result, m.get(1L) % 2 == 1? m.get(1L) : m.get(1L)-1);
        }

        return result;
    }
}

 

 

회고록(막힌 부분)

처음에 키포인트 대칭이기 때문에 2개 이상인것은 잘 잡아냈지만 해당 부분에서 따로 map을 2개 이상인 요소만 따로 리스트에 저장하여 어떻게 풀려고 했다 하지만 해당 부분에서 최대 길이를 구하기 위해 여러 요소들이 존재했기에 구현을 못했다.