[プログラマー]ランキング検索


効率的な課題...やっぱりカカオの問題表面的には単純な体現だが、想像以上に深い概念が要求される問題だ.だから私は効率的ではありません.

1.問題の説明



infoで応募者の情報を入力すると、次のように表示されます.

これらのボランティアをquery変数にフィルタリングする条件を確認します.
以下のように行います.
  • 「java and backend and junior and pizza 100」:javaを使用して符号化テストを行い、後端直系部隊を選択し、初級実務経験のあるsoul foodピザを選択した応募者のうち1人が100点以上の符号化テスト点数を獲得した.
  • 「python and frontend and neighandchicker 200」:pythonを使用して符号化テストを行い、frontend直軍を選択し、ベテランでsoulfood chickerを選択した応募者のうち1人が符号化テスト点数200点以上を獲得した.
  • 「cpp and higher and pizza 250」:cppでコードテストを行い、高級な仕事経験がありsoul foodピザを選んだ応募者のうち、250点以上を獲得した応募者は1人だった.
  • "-and backend and higher and-150":バックエンドスタッフを選択し、ベテランボランティアのうちコードテストの点数が150点を超えた人は1人だった.
  • 「与与与与与鶏100」:soulfoodrochickenを選んだボランティアのうち、コードテスト点数が100点を超えたボランティアは2名.
  • ここで確認したボランティアの定員を順番に取り戻せます.[1,1,1,1,2,4]

    2.難しいところ


    1)二分探索


    この試みを使うとは全く思わなかった.この探索モジュールの対分は単独で位置決めする必要がある.

    3.問題を解く


    0)アイデアの回答


    まずは基本的に科学技術ブログ記事を参考にしました.Kakao問題はよく解説を確認して、推測が間違っているかどうかを見なければなりません.わけがわからず、理解できないコードであれば、正しく解読することはできません.問題はいつも要求がある.
  • ボランティア仕様を含む情報配列で、1行を見ます
  • この応募者は、次のクエリに満足している応募者であり、該当するクエリがあれば計算されます.

    ここのすべての要素で計算できます.
  • つまり、ボランティアが満たすことができるすべての要求を制定しました.
    ボランティア一人一人の点数を集めるだけでいいです.
    したがって、特定の要件が要求された場合、その要件を満たすスコアを決定します.
    一定の点数以上の区間を見つけて戻ってくるのが、満足するボランティアの数です.
    このとき区間を探すときは,二分探索を利用する.

    1)メインプール

    def confirm_employee(info_list, require_info, score):
        cnt = 0
    
        for i in info_list:
            info_row = i.split()
            for info, require in zip(info_row[:4], require_info[:4]):
                if info not in require:
                    if require == "-":
                        pass
                    else:
                        break
            else:
                if int(info_row[-1]) >= int(score):
                    cnt += 1
    
        return cnt
    
    
    def solution(info, query):
        result = []
    
        for i in query:
            require_info = i.replace(" and", "").split()
            result.append(confirm_employee(info, require_info, require_info[-1]))
        return result
    条件を分けて,実際の情報リストと逐一比較した.もちろん効率は通らない

    2)次解

    from collections import defaultdict
    from itertools import combinations
    from bisect import bisect_left
    
    result = []
    employee_dict = defaultdict(list)
    
    def extract_way_underbar():
        global result
        for i in range(1,5):
            for way in combinations([0,1,2,3],i):
                result.append(way)
                
    def extract_info(info_list):
        global result
        global employee_dict
        
        extract_way_underbar()
        for info_each in info_list:
            employee_split = info_each.split()
            for underbar_list in result:
                temp = employee_split
                for change_underbar in underbar_list:
                    temp[change_underbar] = "-"
                    
                key = ''.join(temp[:4])
                if employee_dict.get(key):
                    employee_dict[key].append(int(temp[-1]))
                else:
                    employee_dict[key] = [int(temp[-1])]
        
        for val in employee_dict.values():
            val.sort() 
        
    def solution(info, query):
        global employee_dict
        extract_info(info)
        answer = []
        
        for i in query:
            require_info = i.replace(" and", "").split()
            score, require_info_str = int(require_info[-1]), ''.join(require_info[:4])
            
            if require_info_str in employee_dict:
                potential_employee_score = employee_dict[require_info_str]
                index = bisect_left(potential_employee_score, score)
                answer.append(len(potential_employee_score) - index)
            else:
                answer.append(0)
                continue
    
    
        return answer
    文章を読んで理解してからもう一度解いた.しかし、以下のような解釈は得られなかった.別のブログのページを持って、出力内容を比較しました.
  • その他のブログ出力
  • 私のコード

    ディック・シャナリーの身長はすべての状況の数字を反映していない.よく見ると、ちゃんとコピーしていなかった.
  • temp = employee_splitこの部分で、このようにしてtempの要素を変えると、employee splitの要素も変わります.
    Pythonの浅いコピー、深いコピー部分の位置決めはもうできましたので、必要な人は参考にしてください.
    とにかくこの部分をtemp = list(employee_split)に変えました
    これでは、ほとんどの場合の数字が適用されますが、不足しています.

    よく見ると「-」を適用しなくてもキーで挿入します.だからこの部分を修正したら完成!!

    3)3回目の解

    from collections import defaultdict
    from itertools import combinations
    from bisect import bisect_left
    
    result = []
    employee_dict = defaultdict(list)
    
    
    def extract_way_underbar():
        global result
        for i in range(1, 5):
            for way in combinations([0, 1, 2, 3], i):
                result.append(way)
        result.append(())
    
    
    def extract_info(info_list):
        global result
        global employee_dict
    
        extract_way_underbar()
        for info_each in info_list:
            employee_split = info_each.split()
            for underbar_list in result:
                temp = list(employee_split)
                for change_underbar in underbar_list:
                    temp[change_underbar] = "-"
    
                key = ''.join(temp[:4])
                if employee_dict.get(key):
                    employee_dict[key].append(int(temp[-1]))
                else:
                    employee_dict[key] = [int(temp[-1])]
    
        for val in employee_dict.values():
            val.sort() # 시간이 된다면, 여기서도 깊은복사 얕은 복사의 개념을 숙지해두면 좋겠다. 왜 val만 바꾸는데 딕셔너리 전체에 반영이 되는걸까?
    
    
    def solution(info, query):
        global employee_dict
        extract_info(info)
        answer = []
    
        for i in query:
            require_info = i.replace(" and", "").split()
            score, require_info_str = int(require_info[-1]), ''.join(require_info[:4])
    
            if require_info_str in employee_dict:
                potential_employee_score = employee_dict[require_info_str]
                index = bisect_left(potential_employee_score, score)
                answer.append(len(potential_employee_score) - index)
            else:
                answer.append(0)
                continue
    
        return answer
    解いてみると概念がたくさんあることに気づきました...一つの概念一つの概念がうまく身につけなければ解けない問題だが、概念を知っていれば解けない問題だ.
    カオは本当に出題が上手なようです.変な概念を要求せず、正規課程だけで出題するのは本当に難しい.コット界の評価員みたいな感じ...
    とにかく今日のポジションは終わりました