プログラマー2021 KAKAO BLIND RECRUITMENTランキング



問題の説明が長すぎます.リンクを参照してください.
https://programmers.co.kr/learn/courses/30/lessons/72412

プール(効率ゼロ)

def solution(_info, _query):
    answer = []
    infoList = list(map(lambda x: x.split(' '), _info))
    queryList = list(map(lambda x: x.replace('and ', ''), _query))
    queryList = list(map(lambda x: x.split(' '), queryList))
    queryset = list([set([]) for _ in range(5)] for _ in range(len(queryList)))
    for i, query in enumerate(queryList):
        for j in range(len(query)):
            for info in infoList:
                if query[j].isdigit():
                    if int(query[j]) <= int(info[j]) or query[j] == '-':
                        queryset[i][j].add(' '.join(info))
                else:
                    if query[j] == info[j] or query[j] == '-':
                        queryset[i][j].add(' '.join(info))

    for q in queryset:
        winning = q[0] & q[1] & q[2] & q[3] & q[4]
        cnt = 0
        for w in winning:
            cnt += _info.count(w)
        answer.append(cnt)
    return answer
  • infoとqueryスライスをリストとして保存し、
  • セット5つのリストをクエリー数
  • にマージ
  • クエリでは,言語職業群が食事の点数を経験する順に,同じものを対応する位置の集合に入れる,
  • .
  • とsetの交差を求めると、クエリ条件を満たす人の情報がsetに含まれる.
  • infoには同じ人が複数いるかもしれません.
    inputとしてのinfoではsetのinfoが何個あるかを数えて、そのクエリを満たす人数を得ることができます.
  • 正確性テストはすべて正しいですが、効率はすべて時間を超えているので、他の人の解答を調べました.

    他人を解く

    from itertools import combinations
    
    def solution(info, query):
        answer = []
        db = {}
        # 모든 경우의 수 만들기
        for i in info:
            temp = i.split(' ')
            condition = temp[:-1]
            score = int(temp[-1])
            for n in range(5):
                combi = list(combinations(range(4), n))  # (0,1,2,3) 중에서 n개 뽑기
                for c in combi:
                    temp_con = condition[:]
                    for switch in c:
                        temp_con[switch] = '-'
                    key = ''.join(temp_con)
                    # 같은 것들 그룹화 해서 딕셔너리에 넣어 주기
                    if key in db:
                        db[key].append(score)  # 문자열이 있으면 그 그룹에 점수 추가하고
                    else:
                        db[key] = [score]  # 문자열이 없으면 그룹을 만들고 점수 추가
        # 딕셔너리 모든 값들 그룹별로 정렬
        for value in db.values():
            value.sort()
    
        for q in query:
            # 쿼리 파싱
            temp_q = q.replace('and ', '').split(' ')
            q_condition = ''.join(temp_q[:-1])
            q_score = int(temp_q[-1])
    
            # 쿼리가 딕셔너리에 존재하면
            if q_condition in db:
                data = db[q_condition]
                if len(data) > 0:          
                    start, end = 0, len(data)     # lower bound 알고리즘 통해 인덱스 찾고,
                    while start != end and start != len(data):
                        if data[(start + end) // 2] >= q_score:
                            end = (start + end) // 2
                        else:
                            start = (start + end) // 2 + 1
                    answer.append(len(data) - start)      # 해당 인덱스부터 끝까지의 갯수가 정답
            else:
                answer.append(0)
    
        return answer
    
    まずinfoを条件と点数に分けます
    任意の場合、コンビネーションを使用して作成できます.
    ディック・シャナリーの身長単位で、点数を値に(グループ化)
    例えばjava後端初級ピザ150であれば、
    java/backend/junior/pizza
    -/backend/junior/pizza
    java/-/junior/pizza
    {...}
    -/-/-/pizza
    -/-/-/-
    このように16個の組み合わせを作り、鍵で置いておきます.
    ベル類を採点して、この時グループを分けて、リストに並べます
    その後、ディックシャナリーキー値に基づいてすべてのベルをソートします(バイナリナビゲーションのために)
    クエリがディック郡に存在する場合
    それらのデータを受け取る
    バイナリ・ナビゲーション・アルゴリズムの1つです.下限アルゴリズムです.
    最小値のインデックスを見つけます.
    そのインデックスから、個数を答えに入れればいいのです.
    ポイントはバイナリナビゲーションを使用することです.
    値を検索するのではなく、その値以上の最小値を検索する必要があります.
    下界アルゴリズムを用いて効率を向上させる.
    正確性は容易な問題のようだが、効率性は難しすぎるようだ.
    これはlvです.2;