575. Distribute Candies

리트코드 575번 풀이

문제

Distribute Candies

풀이

아이디어

복잡하게 생각했는데 간단한 문제였다.

• Set을 이용해 고유한 사탕의 종류를 구한다.
• 고유한 사탕의 종류가 n/2보다 작으면 고유한 사탕의 종류가 최대값이 된다.
• 고유한 사탕의 종류가 n/2보다 크거나 같으면 n/2가 최대값이 된다.

코드

function distributeCandies(candyType: number[]): number {
  const set = new Set(candyType);
  const halfN = Math.floor(candyType.length / 2);

  if (set.size < halfN) return set.size;
  return halfN;
}

시간 / 공간 복잡도

• 시간 복잡도: O(n) — Set 생성에 n번 순회
• 공간 복잡도: O(n) — Set에 최대 n개 저장

여담

물론 바쁘게 문제 풀 때는 어쩔 수 없지만, 문제 풀이를 마친 뒤에는 좀 더 깔끔하고 명료하게 작성할 수 있는지를 확인해보는게 좋겠다. 이번 문제도 if문 없이 Math.min을 이용해서 더 명확하게 작성할 수 있었다.

function distributeCandies(candyType: number[]): number {
  const set = new Set(candyType);
  const halfN = Math.floor(candyType.length / 2);

  return Math.min(set.size, halfN);
}