575. Distribute Candies

https://leetcode.com/problems/distribute-candies/

Distribute Candies - LeetCode

난이도 : easy

문제

앨리스가 먹을 수 있는 캔디의 종류의 최대값을 구하여라.

 

해당 문제는 이중 반복문으로 O(N^2) 의 시간으로도 풀수 있다. 여러 접근 방법이 있는데 필자는 unordered_map 을 사용하여 중복되는 요소를 제거하고 어레이의 크기 / 2 두 가지 수를 구하여 더 작은 값을 반환하였다. 

 

코드

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        unordered_map<int, int> m;
        for(auto a:candyType) {
            m[a]++;
        }
        
        int size = candyType.size() / 2;
        
        return (int)min(size, (int)m.size());
    }
};

 

벨류를 갖고 있을 필요가 없음으로 set 을 사용해 보았다.

    int distributeCandies(vector<int>& candyType) {
        unordered_set<int> st;
        for(auto a:candyType) {
            st.insert(a);
        }
        
        return min((int)st.size(), (int)candyType.size() / 2);
    }

 

메모리는 큰 차이가 없고 Runtime 이 조금더 빨라졌다. ㅇㅇ; 정렬을하고 이전 수와 다음수가 다르면 체크해서 count 하고 마지막에 candType.size() / 2 와 비교해도 해당 문제는 풀 수 있어 보인다. 귀찮아서 패스 pass -o-