Q3. ランキング検索

Programmersによって公開された問題によってアルゴリズムを改善することを望んでいる.
アルゴリズム上の脆弱性やより簡潔なアイデアがあれば、いつでも指摘してください.

1.質問のタイプ

問題の説明


問題とI/O例

問題の詳細については、Programmerを参照してください.
https://programmers.co.kr/learn/courses/30/lessons/72412

2.ソースコード

Pythonを使用して作成された完全なコードは次のとおりです.

from bisect import bisect_left
from itertools import combinations

def makeCase(info):
    cases = []
    
    for idx in range(5):
        for combi in combinations([0,1,2,3],idx):
            tmp = ''
            for n in range(4):
                if n in combi:
                    tmp += info[n]
                else:
                    tmp += '-'
            cases.append(tmp)
    return cases


def solution(info, query):
    answer = []
    dic = dict()
    
    for i in info:
        splitInfo = i.split()
        combi = makeCase(splitInfo)
        
        for cb in combi:
            if cb in dic:
                dic[cb].append(int(splitInfo[4]))
            else:
                dic[cb] = [int(splitInfo[4])]
    
    for key in dic.keys():
        dic[key].sort()
    
    for q in query:
        splitQuery = q.split()
        target = splitQuery[0]+splitQuery[2]+splitQuery[4]+splitQuery[6]
        value = int(splitQuery[7])
        
        if target in dic:
            ans = len(dic[target])-bisect_left(dic[target],value,lo=0,hi=len(dic[target]))
            answer.append(ans)
        else:
            answer.append(0)
    return answer

3.問題を解く

簡潔な論理はいくつかあるが,本人はすべてのグループの合併を発見することによって結果を導く方法で問題を解決した.
コアライブラリ

from itertools import combinations
from bisect import bisect_left

組合せ:ライブラリ関数

、組合せを検索し、すべてのペアをDictionaryに返す

対分left:リストにxを挿入してバイナリ分割アルゴリズムのソートを維持するインデックス

を返すライブラリ関数
以上の2つのライブラリ関数がこの問題を解決する鍵であると考えられます.
しゅろんり

3-1 makeCase関数

def makeCase(info):
    cases = []
    
    for idx in range(5):
        for combi in combinations([0,1,2,3],idx):
            tmp = ''
            for n in range(4):
                if n in combi:
                    tmp += info[n]
                else:
                    tmp += '-'
            cases.append(tmp)
    return cases

関数名は任意に取得されますが、関数の役割はparamで、指定されたlistに基づいてすべてのグループを作成して返します.

最初のfor文:結合を作成する要素(=idx)を指定します.この問題では,点数のほかに4つの要因があり,(0から4)が範囲と考えられる.

2 2 2番目のfor文:組合せ関数によって組合せを作成します.[0,1,2,3]は、idx個で作成された組合せを返します.
ex)idx=0:組み合わせなし->combi==
ex)idx==4:すべて使用->tmp="(0、1、2、3)

第3のfor文:現在の値(=n)を組み合わせて作成した組合せに含まれている場合、インデックス(=n)に対応するinfo[n]がtmp変数に追加されます.
含まない場合は、tmpに「-」を追加します.

複雑に見えるが,結果的に,与えられた情報のすべての組合せを探す過程といえる.

3-2主関数

def solution(info, query):
    answer = []
    dic = dict()
    
    for i in info:
        splitInfo = i.split()
        combi = makeCase(splitInfo)
        
        for cb in combi:
            if cb in dic:
                dic[cb].append(int(splitInfo[4]))
            else:
                dic[cb] = [int(splitInfo[4])]
    
    for key in dic.keys():
        dic[key].sort()
    
    for q in query:
        splitQuery = q.split()
        target = splitQuery[0]+splitQuery[2]+splitQuery[4]+splitQuery[6]
        value = int(splitQuery[7])
        
        if target in dic:
            ans = len(dic[target])-bisect_left(dic[target],value,lo=0,hi=len(dic[target]))
            answer.append(ans)
        else:
            answer.append(0)
    return answer

辞書

に保存

    dic = dict()
    
    for i in info:
        splitInfo = i.split()
        combi = makeCase(splitInfo)
        
        for cb in combi:
            if cb in dic:
                dic[cb].append(int(splitInfo[4]))
            else:
                dic[cb] = [int(splitInfo[4])]

3−1では,makeCase(info)が受け取った組合せに従って辞書格納動作を行う.
この場合,int型でlistに強制変換する理由は以下のとおりである.

辞書に格納されている値は、昇順で

に並べ替えられます.

for key in dic.keys():
	dic[key].sort()

keyのvalue(=list)をソートします.整数型なので、数字の大きさ関係で昇順に並べ替えられていることがわかります.

[条件]を満たす人のうち、コードテストX点以上を取得した人は何人いますか?

    for q in query:
        splitQuery = q.split()
        target = splitQuery[0]+splitQuery[2]+splitQuery[4]+splitQuery[6]
        value = int(splitQuery[7])
        
        if target in dic:
            ans = len(dic[target])-bisect_left(dic[target],value,lo=0,hi=len(dic[target]))
            answer.append(ans)
        else:
            answer.append(0)

前述したようにbisect left関数は、ソートリストにxという値がある場合、その値を含むべきインデックスを返します.
これが問題解決のキーワードといえる.
例
ex)生徒ごとに10,20,30,40,50点を獲得した場合,35点以上の生徒数を獲得すれば40,50点を獲得した2名である.
indexを基準として、35点の位置は3を指すべきです.

総学生数(5)−35が入るべき位置(3)=35点以上を得る学生数(2)

len(students) - bisect_left(student,35,~,~) = 2

原理は上記のように見なすことができる.
したがって,これを本題に代入すれば,X点以上の学生数を得ることができる.
もっと分かりやすいのは、書く能力が足りないので難しいかもしれませんが...ううう

4.運転結果

上記の原理に従って作成した結果を返すと,次のように通過することが分かる.

5.終了

今日は組み合わせと対分leftで問題を解きます.
確かにPythonはアルゴリズムを解く上で人にやさしい言語のようだ.様々なライブラリを通じて簡便性を提供するとともに、多くの知識を身につければ、これ以上の言語はありません.
初心を失わないで、前進し続けなさい.
完全なソースGitリンク
https://github.com/cho876/Algorithm/blob/master/Problem/Kakao/2021_kakao_blind_recruitment_q3.py