完走していない選手-JavaScriptの説明

👉 Programmers問題リンク

論理1

完走(完走)の並びから順に1名を抽出した.

の完走者の名前を参加者(参加者)が並ぶ前から順に比較する.
2-1. 同じ名前がある場合は、参加者配列から名前を削除します.

の全完走コースの配列に対して1-2の過程を繰り返す.

は、すべてのカリキュラムの終了後に参加者の配列の残りの要素を返します.

次のコードに実装します.

function solution(participant, completion) {
  
   // 완주자 배열에서 1명씩 이름을 꺼내 name_completion에 저장     
   for(let i = 0; i < completion.length; i++){
       let name_completion = completion[i];
     
       // name_completion을 참가자 배열의 모든 이름과 비교
       for(let j = 0; j < participant.length; j++){
           let name_participant = participant[j];
           
           // 참가자 배열에 name_completion과 동일한 이름이 있을 경우 해당 이름을 배열에서 삭제
           if(name_completion === name_participant){
               participant.splice(j,1); 
               break;
           }
       }
   }
    
    return participant.pop(); // 참가자 배열에 남은 요소가 완주하지 못한 선수가 된다.
}

上記コードを実装することで所望の結果が得られるが、このコードは効率的に問題がある.
完了者数に等しい繰返しを有する繰返し文には、O(n^2)の時間複雑度を有する参加者数に等しい繰返し文が存在する.
与えられた問題では,参加可能な選手数の最大値は10万であり,n=10万であればn^2=100億であり,時間制限があれば正確な結果を出すことは難しい.(通常、計算時間の複雑度が1億であれば1秒かかる)
だから、別の方法を考える必要がある.

解題ロジック2

比較時間を最大限に短縮するために,与えられた配列を予め並べ替える方法を試みた.
sort()法を用いて

全行程を完走した選手と参加者をソートした.

参加者配列の長さに従って繰り返し文を実行し、同じ位置(インデックス)の完走者配列と参加者配列の要素を比較します.
2-1. インデックス内の2つの配列の要素が異なる場合は、その要素が返されます.

問題の条件によると、完走と参加者の手配の要素は完走していない選手1人だけが異なる.したがって,2つの配列を並べ替えて比較すると,下図のように完走していない選手のインデックスは,2つの配列が一致しない場合のインデックスを初めて求めることができる.

次のコードに実装します.

function solution(participant, completion) {
    var answer = '';
        participant.sort();
        completion.sort();

        for(let i = 0; i < participant.length; i++){
            if(participant[i] !== completion[i]){
                return answer = participant[i]
            }
        }
}

上記のコードの時間的複雑さを実現するために、まずfor文を表示する.このfor文は参加者配列の長さだけを繰り返すため、O(n)の時間的複雑さを有する.問題はsort()メソッドの時間的複雑さであり,これは異なる言語で異なる実装があり,javascriptではO(nlogn)の複雑さがある.従って,このアルゴリズムの時間的複雑さはO(nlogn)であった.
nの最大値は10万であるため,底部が2のログに対して時間複雑度を計算するとnlognが166であるだけで前のプールの100億よりはるかに小さい値が得られる.したがって,このアルゴリズムは有効なアルゴリズムであると考えられる.