名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。

No.349 干支の置き物

No.349 干支の置き物 - yukicoder

絶対に隣りあわないパターンかどうかを判断する問題。


もしこの中で一番多い種類を考えると、ABABABABAのように1つ置きにAが現れるパターンが最大で、これを超えてしまうと絶対どこかで隣り合ってしまう。
よって一番多い種類が(n+1)//2個以下であればYES、そうでなければNOを出力する。


ちなみにこの類のカウントする問題は、Pythonを使っている場合、Counterを使うことで少し楽に処理が可能である。


以下、Python3での解答コード。

#81004 No.349 干支の置き物 - yukicoder

from collections import Counter
n = int(input())
c = Counter([input() for _ in range(n)])
print("YES" if (n+1)//2>=max(c.values()) else "NO")