[アルゴリズム]プログラマー-完走しなかった選手

🏃🏻 完走していない選手

問題の説明

多くのマラソン選手がマラソンに参加した.1人の選手を除いて、すべての選手がマラソンを完走した.
マラソンに出場する選手の名前と完走した選手の名前の並びが完成したら、完走していない選手の名前を返す解決関数を書いてください.

せいげんじょうけん

マラソンに出場する選手は1人以上10万人以下だ.

完了長さは参加者の長さ1より小さい.

参加者の名前には、少なくとも1つまたは20個の小文字が含まれています.

参加者は同名であってもよい.

I/O例

participantcompletionreturn["leo", "kiki", "eden"]["eden", "kiki"]"leo"["marina", "josipa", "nikola", "vinko", "filipa"]["josipa", "filipa", "marina", "nikola"]"vinko"["mislav", "stanko", "mislav", "ana"]["stanko", "ana", "mislav"]"mislav"

I/O例説明

例1
「leo」は参加者名簿に載っているが、フルコースを走る者名簿には載っていないため、フルコースを完走できなかった.
例2
「vinko」は参加者名簿に載っていたが、完走者名簿に載っていなかったため完走できなかった.
例#3
「誤導」は参加者リストに2人いたが、完走者リストには1人しかいなかったため、1人は完走しなかった.

説明する

最初の解

function solution(participant, completion) {
    let p = participant.filter(x => !completion.includes(x));
    let answer = p.join();
    return answer;
}

正確性テスト

試験1〉合格(0.05 ms,30.1 MB)
テスト2〉失敗(0.05 ms,30.1 MB)
試験3〉合格(0.30 ms,30.1 MB)
試験4〉合格(0.99 ms,30.2 MB)
テスト5〉失敗(1.03ミリ秒、30.3 MB)

こうりつしけん

テスト1〉失敗(タイムアウト)
テスト2〉失敗(タイムアウト)
テスト3〉失敗(タイムアウト)
テスト4〉失敗(タイムアウト)
テスト5〉失敗(タイムアウト)filter()メソッドで参加者から完了した重複データを削除し、未完了の人を一列に並べてみるjoin()メソッドは文字列に変換して答えを返すが、このメソッドでは同有名人を出力できないという問題が発生する.そして効率は完全に破壊された.その結果、同じ名前の未完了の人を出力する場合は、参加者と完了配列を同じようにソートし、インデックス別に比較し、出力が一致しないインデックスの方向に実装する必要があります.

2番目の解

function solution(participant, completion) {
    var answer = '';
    participant.sort();
    completion.sort();
    for(var i = 0 ; i < participant.length; i++){
        if(participant[i] !== completion[i]){
            answer = participant[i];
            break;
        }
    }
    return answer;
}

正確性テスト

試験1〉合格(0.05 ms,30.1 MB)
試験2〉合格(0.08 ms,30.1 MB)
試験3〉合格(0.34 ms,30.1 MB)
試験4〉合格(0.59 ms,30.2 MB)
試験5〉合格(0.63 ms,30.1 MB)

こうりつしけん

試験1〉合格(46.78 ms,41.3 MB)
試験2〉合格(76.78 ms,47.7 MB)
試験3〉合格(96.70 ms,52.2 MB)
テスト4〉合格(106.42 ms,55.1 MB)
試験5〉合格(110.64 ms,53.6 MB)
同じ方法でそれぞれの配列を並べ替える方法を検索すると、Array.prototype.sort()方法が見つかりました.

Array.prototype.sort()

sortメソッドは配列内の要素をソートします.ソースアレイを直接変更し、整列したアレイを返します.sortメソッドのデフォルトでは、要素を昇順にソートします.ハングル文字列としての要素も昇順に並べられています.sort()メソッドで参加者と完了配列をそれぞれ昇順に並べ替え、for文で配列ごとのインデックスを比較します.結果値「回答」がparticipant[i] !== completion[i]の場合、返却すべきparticipant[i]値.これにより、同じ名前でも一致しないインデックスが生成され、正常に完了していない人が返されます.

他人を解く

Map()使用している草

const myMap = new Map();

    for (const participant of participants){
        if(!myMap.get(participant)){
            myMap.set(participant, 1);
        }else{
            myMap.set(participant, myMap.get(participant)+1);
        }
    }

    for(const completion of completions){
        if(myMap.get(completion)){
            myMap.set(completion, myMap.get(completion)-1);
        }
    }
    
    for(const participant of participants){
        if(myMap.get(participant) && myMap.get(participant) >=1 ){
            answer = participant;
        }
    }

使用対象者の回答

function solution(participants, completions) {
    var answer = '';
    

    const obj = {};
    for(const participant of participants){
        if(!obj[participant]){
            obj[participant] = 1;
        }else{
            obj[participant] += 1;
        }
    }
    
    for(const completion of completions){
        if(obj[completion]){
            obj[completion] -=1;
        }
    }
    
    for(const participant of participants){
        if(obj[participant] >= 1){
            answer = participant;
        }
    }

keyで名前を格納し、valueで参加者数を格納します.そして、完走を繰り返してvalueを1に減らします.valueが1より大きい場合は、未完了のユーザを返します.△実は、MapとObjectの勉強がまだ足りないので、コードを見てもあまり理解できません.勉強を続けてから、もう一度理解してください.

参考資料

https://velog.io/@noyo0123/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-javascript-%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80-%EB%AA%BB%ED%95%9C-%EC%84%A0%EC%88%98-otk2fxojro