[プログラマー]ランキングの検索(Pythonプール)

Problem Point

最初に思いついた案は、言語、職業、経歴、魂の食品を開発する順番に対応する案を探ることだ.そして配列の大きさを見るとinfo 5万、query 10万と、時間全体の複雑さがO(nm)でタイムアウトすると予想されています.本当に問題を解いている場合は、正確性だけが合格します.
30分後、Kakafulを見て、何を考えてもいいです.
ココア:https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

上記の表のように、該当するすべてのグループに150点を加えた後、条件があればクエリの点数よりも高い点数を選択できます.

に答える

Kakafoliを見て組み合わせ方を考えた最初は万能条件-度の組み合わせのキーで入れるべきだと思っていたのですが、入れなくても組み合わせは順番を守ってくれるので、単独で入れることはありませんでした.解答からinfo値を分離した後,スコア以外の組合せをグループのキー値とすることが分かる.
グループを接続した後、そのグループのスコアをソートするためにkeys()値を中心にソートします.
最後に、各クエリー文は、クエリーの重要な部分をリストに抽出することを実現し、二分探索は、bisectを使用して、検索するスコア以上のスコアを答えリストに追加する.

最終回答

from collections import defaultdict
from itertools import combinations
import bisect
def solution(info, query):
    answer = []
    group=defaultdict(list)
    for i in info:
        temp=i.split()
        score=int(temp.pop())
        for j in range(0,5):
            for k in combinations(temp,j):
                group["".join(k)].append(score)
    for i in group.keys():
        group[i].sort()
    for i in query:
        temp=i.split(" ")
        search=int(temp.pop())
        temp = [ x for x in temp if x!='and' and x!='-']
        temp = "".join(temp)
        lo=bisect.bisect_left(group[temp],search)
        answer.append(len(group[temp])-lo)
    return answer