PFIの問題の解答(でこすけ)

gistfile1.py

#/usr/bin/python
# coding:utf-8

"""
PFIブログの問題
http://research.preferred.jp/2011/07/intern2011_problem/
の解答。アイディアとしては
・最大になる文字の候補を２つに絞る
・それぞれの候補に対して、候補が実際に文字列の半分以上あるか調べる
の２ステップで行う。
最初のステップは、ハッシュ「data」に
data[文字種] = その文字の今までの出現数
になるようにハッシュを作っていくことで行う。

ただし、ハッシュのキー数が２つを超えないように以下の工夫をしている。
文字を挿入した後に、キー数が３つ以上なら
data[ 1番出現数の少ない文字 ] を削除
data[ 2番目に文字出現数の少ない文字] から、先ほど削除したデータと同数だけ減らす
（つまり、２種類の文字の出現数をペアで同数だけ減らす）

問題の条件より、最大になる文字は全体の半分を超えている。
この作業で最大になる文字文字が候補から消えてしまったとすると、
少なくても同数のそのほかの文字が消えていることになるが、これは矛盾する。
よって背理法より一番出現数の多い文字は最後に必ず残る。

計算量などの評価：
計算量O(N)
外部メモリ量O(1)
"""

strings = ["sasasas","sasbscs","aaabbbsssssss", "sasbsbsbsbsbsbs", "sbbbssass","ssssabc","sasbsscsd"]

data = {}

def push(achar):
  global data
  if data.has_key(achar):
    data[achar]+=1
  else:
    data[achar]=1
    if len(data.keys())>=3: #3要素以上になったらかならず１要素以上消すルーチン
      data_sorted = sorted(data.items(), key=lambda x:x[1]) #(key,valu)の組リストを値の降順で作る
      minval = data_sorted[0][1]
      del(data[data_sorted[0][0]]) #1番valueの小さい要素を削除
      if data_sorted[1][1]==minval:
        del(data[data_sorted[1][0]]) #2番目と1番目のvalueが同じなら両方削除
      else:
        data[data_sorted[1][0]]-=minval #2番目に小さい要素から1番目と同じ分だけ削る

def find_max(astr):
  global data
  data = {}
  for achar in astr:
    push(achar) #メインルーチン。候補を最大2つに絞る
    #print achar,data
  for elem in data.keys(): #最大2つの候補から順番に、半分以上あるか調べる
    count = 0
    for achar in astr:
      if achar==elem:
        count+=1
    if count>len(astr)/2:
      print 'maximum char of "'+astr+'" is "'+elem+'"'
      return

for string in strings: #実行例
  find_max(string)