Pythonでリストから準優勝のスコアを求めるプログラム

複数の参加者のスコアがリスト形式で与えられたとき、その中から「準優勝」、つまり2番目に大きいスコアを見つける方法を解説します。

たとえば scores = [5, 8, 2, 6, 8, 5, 8, 7] という入力の場合、最高得点は8なので、準優勝のスコアは7となり、出力は 7 になります。

アルゴリズムの考え方

この問題は、以下の手順で解くことができます。

• 優勝スコアを表す winner と、準優勝スコアを表す runner_up を、ともに -99999 など十分に小さい値で初期化します。
• スコアリストの各要素 i について、次の処理を繰り返します。
  • i が winner より大きい場合：これまでの winner を runner_up に退避させ、winner を i で更新します。
  • i が winner 未満かつ runner_up より大きい場合：runner_up を i で更新します。
• すべての要素を処理し終えたら、runner_up を返します。

ここでのポイントは、新しい優勝候補が現れたときに、それまでの winner を runner_up へ「繰り下げる」ことです。これにより、同じ最大値が複数回出現するケース（上の例では8が3回出現）でも、正しく準優勝の値を求められます。

実装例

理解を深めるために、実際のコードを見てみましょう。

def solve(scores):
   winner = -99999
   runner_up = -99999
   for i in scores:
      if (i > winner):
         winner, runner_up = i, winner
      elif (i < winner and i > runner_up):
         runner_up = i
   return runner_up

scores = [5, 8, 2, 6, 8, 5, 8, 7]
print(solve(scores))

入力

[5, 8, 2, 6, 8, 5, 8, 7]

出力

7

別のアプローチ：setとsortedを活用する方法

Pythonでは、重複を除去してからソートするという、よりシンプルな書き方もあります。

def solve(scores):
   unique_scores = sorted(set(scores))
   return unique_scores[-2]

scores = [5, 8, 2, 6, 8, 5, 8, 7]
print(solve(scores))

set() で重複するスコアを取り除き、sorted() で昇順に並べ替えたうえで、末尾から2番目の要素（インデックス -2）を取得すれば、準優勝のスコアが得られます。コードは短くなりますが、ソートに O(n log n) の計算量がかかる点には注意してください。一方、最初に紹介した線形探索による方法は O(n) で動作するため、データ数が多い場合により効率的です。

まとめ

準優勝スコアの取得は、「現在の優勝値と準優勝値を常に追追跡しながらリストを一度だけ走査する」ことで効率的に実現できます。状況に応じて、計算量を抑えた線形探索版と、可読性の高いset＋sort版を使い分けるとよいでしょう。