【Python】レベルアップ問題集「ソートと検索(query)」のコーディングを工夫する

問題

paizaラーニング - レベルアップ問題集 - クエリメニュー - Python編 - ソートと検索(query)
難易度：paizaランク D 相当

プログラミング練習問題「ソートと検索 (query)」

実装

愚直に組む

初回の挑戦時、題意どおり（と信じて）組んだところ、テストケース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ともに万単位のクエリ行があり、律儀にソートしていては間に合わないことがあるのです。
※クラウドの混雑具合にもよるのかもしれません。後日同じコードでジャッジに通ってしまいました（下図）

実行時間：1.63秒（場合により2秒以上かかる可能性あり？）

コーディングを工夫する

次のように、実行時間を短縮する工夫をしてみました。

• コンストラクタ：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

実行結果

めでたく実行時間が短縮されました。オンラインジャッジのテストケースではこれで十分でしょう。

実行時間：0.88秒。約半分に短縮成功

オチ

実はここまでしなくても「答え」自体は出せます。ただ、解答・コード例を読んで納得行かなかったので、「意地でもソートしてやる！」と奮起してやってみました。これでスッキリしました。