Mochi

가장 많이 등장하는 크기의 등장 횟수를 $F$라고 하자. 한 묶음에는 서로 다른 크기의 떡 두 개가 필요하다.

어떤 크기가 $F>N/2$번 등장한다면 그 크기의 떡은 다른 크기의 떡과만 묶을 수 있으므로 최대 $N-F$개를 만들 수 있다. 반대로 $F\leq N/2$라면 가장 많은 크기도 나머지 떡들과 충분히 짝지을 수 있어 $\lfloor N/2\rfloor$개를 만들 수 있다.

따라서 정답은 $\min(\lfloor N/2\rfloor,N-F)$이다. 빈도만 세면 되므로 해시 맵을 사용하면 기대 시간 복잡도는 $O(N)$이다. Solution written by GPT5.6