【Python】レベルアップ問題集「ソートと検索(query)」のコーディングを工夫する
問題
paizaラーニング - レベルアップ問題集 - クエリメニュー - Python編 - ソートと検索(query)
難易度：paizaランク D 相当
実装
愚直に組む
初回の挑戦時、題意どおり（と信じて）組んだところ、テストケース4でタイムアウトしてしまいました（スクショ忘れ）。
クラス宣言部
コンストラクタ：次のインスタンス変数を用意する
paiza君の身長 paiza_tall
クラスの生徒の身長を入れるリスト retsu
join()メソッド：転入生の身長を retsu に追加する
sorting()メソッド：リスト retsu をソートし、paiza君の位置を表示する
event()メソッド：クエリリストの先頭要素により条件分岐してjoin()かsorting()いずれかのメソッドを呼び出す
pos_paizakun()メソッド：paiza君の位置を返す
class Classroom:
def __init__(self, paiza):
self.paiza_tall = paiza
self.retsu = [paiza]
def join(self, tall):
self.retsu.append(tall)
def sorting(self):
self.retsu.sort()
print(self.pos_paizakun())
def event(self, strs:list):
command = strs[0]
if command == "join":
self.join(int(strs[1]))
elif command == "sorting":
self.sorting()
else:
print("unknown event")
def pos_paizakun(self):
return self.retsu.index(self.paiza_tall) + 1
メインルーチン
n, k, p = map(int, input().split())
classroom = Classroom(p)
for _ in range(n):
classroom.join(int(input()))
for _ in range(k):
line = list(map(str, input().split()))
classroom.event(line)
なぜマズいのか
条件では 1 ≦ N, K ≦ 100,000 という点に注意が必要です。実際にテストケース4はN, Kともに万単位のクエリ行があり、律儀にソートしていては間に合わないことがあるのです。
※クラウドの混雑具合にもよるのかもしれません。後日同じコードでジャッジに通ってしまいました（下図）
コーディングを工夫する
次のように、実行時間を短縮する工夫をしてみました。
コンストラクタ：paiza君より低い身長のリスト・paiza君より高い身長のリストを新たに用意する
join()メソッド：転入生の身長に応じて「低い身長のリスト」「高い身長のリスト」に振り分ける
sorting()メソッド：「低い身長のリスト」「高い身長のリスト」を別々にソートする
class Classroom:
def __init__(self, paiza):
self.paiza_tall = paiza #paiza君の身長
self.shorter_than = [] #paiza君より低い身長のリスト
self.taller_than = [] #paiza君より高い身長のリスト
def join(self, tall):
if tall < self.paiza_tall:
self.shorter_than.append(tall)
elif tall > self.paiza_tall:
self.taller_than.append(tall)
else:
return
def sorting(self):
self.shorter_than.sort()
self.taller_than.sort()
print(self.pos_paizakun())
def event(self, strs:list):
command = strs[0]
if command == "join":
self.join(int(strs[1]))
elif command == "sorting":
self.sorting()
else:
print("unknown event")
def pos_paizakun(self):
return len(self.shorter_than) + 1
実行結果
めでたく実行時間が短縮されました。オンラインジャッジのテストケースではこれで十分でしょう。
オチ
実はここまでしなくても「答え」自体は出せます。ただ、解答・コード例を読んで納得行かなかったので、「意地でもソートしてやる！」と奮起してやってみました。これでスッキリしました。