Programmers#ランキング検索

LEVEL :
Level2
質問の概要:
これは2021年に提出されたKakaoTalk符号化試験問題である.
指定された値を文字列で処理することで、クエリーの問題を正確かつ効率的に処理できます.
ソリューション:
最初の考えは二つある.setで各領域を交差させる方法としては、dictionaryでinfo値を処理してキー値とする方法が2つあります.初めてsetで解決するのは非常に簡単で,精度は100%であったが,効率面では通過せず,最終的にdictionaryを用いる方法に移行した.最初、辞書にはinfoで指定された値しか含まれていません.たとえば、lang={"java":"1","python":"2"},food={
"chicken":"1","pizza":"2"},..など、このように予め実現された後、info値を1212と同じキー値に設定し、その領域に含まれるスコアをlistとして保存する.しかし、このようにすると、私たちは「-」のような問題を解決せざるを得ず、処理も非常に面倒になり、このように{java,pizza,...}「-」を組み合わせて、複数の場合の数字を求め、各キー値が16の場合の数字を求める.その後、queryの値を使用して領域内のすべてのスコアのリスト値をロードし、lognの速度で二分検索することができます.
かなり難しい問題のようです.
ソリューション1-setの交差->効率の失敗

import re

def findCount(num,arr) :
    cnt = 0
    for i in range(len(arr)) :
        if num <= arr[i][1] :
            cnt+=1
    return cnt
def solution(info, querys):
    res = []
    lang = {"cpp":[],"java":[],"python":[],"-":[]}
    job = {"backend":[],"frontend":[],"-":[]}
    career = {"junior":[],"senior":[],"-":[]}
    food = {"chicken":[],"pizza":[],"-":[]}
    
    info = [list(info[i].split()) for i in range(len(info))]
    querys = [list(re.split(" and | ",querys[i])) for i in range(len(querys))]

    for i in range(len(info)) :
        uid = i
        user_score = int(info[i][4])
        lang[info[i][0]].append((uid,user_score))
        lang["-"].append((uid,user_score))
        job[info[i][1]].append((uid,user_score))
        job["-"].append((uid,user_score))
        career[info[i][2]].append((uid,user_score))
        career["-"].append((uid,user_score))
        food[info[i][3]].append((uid,user_score))
        food["-"].append((uid,user_score))
        
    for query in querys :
        intersection = list(set(lang[query[0]]) & set(job[query[1]]) & set(career[query[2]]) & set(food[query[3]]))
        res.append(findCount(int(query[4]),intersection))
        return res

ソリューション2-すべての場合bsをナビゲート

from itertools import combinations 

def findCount(arr,num) :
    arr_len = len(arr)
    if arr_len > 0 :
        left,right = 0,len(arr)
        while left < right:
            mid = (left + right) // 2
            if num > arr[mid]:
                left = mid + 1
            else:
                right = mid 
    return arr_len-left
def solution(info, querys):
    res = []
    dic = {}
    for info_list in info :
        query = info_list.split()
        dic_key = query[:-1]
        score = int(query[-1])
        for i in range(5) :
            for key in combinations(dic_key, i) :
                    new_pattern = ''.join(key)
                    if new_pattern in dic :
                        dic[new_pattern].append(score)
                    else:
                        dic[new_pattern] = [score]
                    
    for i in dic :
        dic[i].sort()

    for query in querys :
        query = query.split()
        score = int(query[-1])
        key = "".join(query[:-1]).replace("-","").replace("and","").replace(" ","")
        if key in dic :
            res.append(findCount(dic[key], score))
        else :
            res.append(0)
    return res

ソース

プログラマー:https://programmers.co.kr/learn/courses/30/lessons/72412