[LeetCode] 사탕 나누기

leetcode.com/explore/challenge/card/march-leetcoding-challenge-2021/588/week-1-march-1st-march-7th/

앨리스는 n 개의 사탕을 가지고 있고, i 번째 사탕은 candyType[i] 타입이라고 합니다. 앨리스는 자신이 살이 찌기 시작하는 것을 알아 차리고 의사를 찾아갔습니다.

의사는 앨리스에게 가진 사탕의 n / 2 개만 먹으라고 조언했습니다 (n은 항상 짝수임). 앨리스는 사탕을 매우 좋아하고 의사의 조언을 따르면서 다양한 종류의 사탕을 최대한 많이 먹고 싶어합니다.

길이 n의 정수 배열 candyType이 주어지면, 앨리스가 n / 2 개만 먹으면 먹을 수있는 다양한 유형의 사탕의 최대 수를 반환합시다.

Example 1:

Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: 앨리스는 6/2 = 3 개의 사탕만 먹을 수 있습니다. 사탕이 3 종류 밖에 없기 때문에 모든 종류를 하나씩 먹을 수 있습니다.

Example 2:

Input: candyType = [1,1,2,3]
Output: 2
Explanation: 앨리스는 4/2 = 2 개의 사탕만 먹을 수 있습니다. 사탕이 3 종류이기 때문에 [1,2], [1,3], [2,3]처럼 두 종류의 사탕만 먹을 수 있습니다.

Example 3:

Input: candyType = [6,6,6,6]
Output: 1
Explanation: 앨리스는 4/2 = 2개의 사탕만 먹을 수 있습니다. 두 종류의 사탕까지 먹을 수 있지만, 사탕이 한 종류 밖에 없네요.

Constraints:

• n == candyType.length
• 2 <= n <= 104
• n is even.
• -105 <= candyType[i] <= 105

힌트 1

사탕 종류의 수를 극대화하려면 앨리스가 같은 종류의 사탕을 최대한 먹지 않아야 합니다.

힌트 2

앨리스가 먹을 수 있는 사탕 종류의 상한은 얼마입니까? 앨리스는 하루에 사탕을 n / 2 개만 먹을 수 있습니다.

힌트 3

사탕 종류의 수를 구하기에 가장 적합한 자료 구조는 무엇일까요?

힌트 4

해시 셋으로 문제가 해결 될까요? 모든 사탕 종류를 해시 세트에 삽입 한 다음 상한으로 크기를 확인합니다.

풀이

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        return min(len(set(candyType)), len(candyType) // 2)

사탕 종류는 candyType에서 중복을 제거한 값입니다. set을 통해 배열에서 중복된 요소를 제거하고 len을 통해 사탕 종류의 수를 구합니다. 이를 n / 2 (= len(candyType) // 2)과 비교하여 더 작은 값을 반환합니다. n / 2와 비교하는 이유는 [1,2,3,4,5,6,7,8]과 같은 경우 사탕은 8종이 있지만, 먹을 수 있는 종류의 수는 4종 밖에 되지 않기 때문입니다.

시간 복잡도 O(1), 공간 복잡도 O(1)