https://codeforces.com/contest/1506/problem/D
시간 2초, 메모리 256MB

input :

• t (1 ≤ t ≤ 104)
• n(1 ≤ n ≤ 2 * 105)
• a1, a2, …, an (1 ≤ ai ≤ 109).

output :

• For each test case, output the minimum possible size of the array after applying some sequence of operations to it.
  각 테스트 케이스에서 얻을 수 있는 가장 작은 사이즈의 배열을 출력하시오.

조건 :

-You can apply the following operation, consisting of several steps, on the array a zero or more times:
you select two different numbers in the array ai and aj;
you remove i-th and j-th elements from the array.
수가 다른 두 원소를 선택하고 배열에서 삭제하는 연산을 0번 이상 수행할 수 있다.

---

생각은 하고 어떻게 해야겠다 까지는 했지만 구현에서 막혀 답을 본 문제이다.

생각을 한 방법은 그냥 반복을 계속 수행하는 방식이였는데 예시에서 1 1 2 2 3 3의 경우 다 다른 수 끼리 제거를 할 수 있는 것처럼 딕셔너리에 저장해서 각각의 수를 매칭하려 했다.
그런데 이런 경우 딕셔너리 키 값을 저장하는 방식 위치를 저장하는 방식에서 어려웠다.

빈도

각 수들의 빈도를 저장해두자.
위의 방식과 비슷하지만 다른 부분은 이것이다. 빈도가 가장 큰 놈들부터 삭제를 하는 것이다. 그러다가 이 빈도 수를 저장한 배열의 길이가 1 혹은 0이라면 멈추는 것이다.

import sys
from heapq import heappop, heappush

for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))
    data.sort()
    temp = dict()
    counts = []

    for item in data:
        if item not in temp:
            temp[item] = 1
        else:
            temp[item] += 1

    for item in temp.keys():
        heappush(counts, -temp[item])

    while len(counts) > 1:
        a = -heappop(counts) - 1
        b = -heappop(counts) - 1

        if a > 0:
            heappush(counts, -a)
        if b > 0:
            heappush(counts, -b)

    print(0 if len(counts) == 0 else -counts[0])