わかさぎのブログ

プログラミング、Atcoderの勉強とか

AtCoder Beginner Contest 058 C - 怪文書

コード

from collections import defaultdict

N=int(input())
s=[]
for i in range(N):
    tmp=list(input())
    s.append(tmp)

data=[]
for i in s:
    tmp=defaultdict(int)
    for j in i: tmp[j]+=1
    data.append(tmp)

setset=[set() for i in range(len(data))]
for i,j in zip(data,setset):
    for k in i.keys(): j.add(k)

common_set=setset[0]
for i in range(1,N):
    common_set=common_set & setset[i]

common=list(common_set)

countcount=[]
for i in common:
    count=100
    for j in data:
        count=min(count,j[i])
    countcount.append(count)

moji=""
for i,times in zip(common,countcount):
    for j in range(times):
        moji+=i

print("".join(sorted(moji)))

考え方

文字列S_iそれぞれについてdefaultdictで何の文字が何文字あるかの辞書を作る。
setの積集合を取って、S_iに共通な文字を抽出。
共通な文字それぞれについて、含む数の最小値を求める。