[プログラマー]レポート結果の取得(JavaScript)

問題の説明

[2022 KAKAO BLIND RECRUITMENT]
新入社員の武志氏は、掲示板の不良ユーザーを通報し、メールで処理結果を送信するシステムを開発しようとした.ムーチが開発するシステムには、次のものがあります.
プレイヤー1人につき1人のプレイヤーしか申告できません.
通報回数を制限しない.異なるプレイヤーを通報し続けることができます.
1人のプレイヤーを複数回通報することができますが、同じプレイヤーに対する通報回数は1回に処理されます.
k回以上通報したプレイヤーは掲示板の使用を中止し、そのプレイヤーを通報したすべてのプレイヤーにメールで停止事実を送信する.
ユーザーが申告したすべての内容を収集し、最後に掲示板の使用を一度に停止し、停止メールを送信します.
以下に、完全なユーザリストが[「muzi」、「frodo」、「apeach」、「neo」、k=2(すなわち、2回以上通報された場合は使用を停止する)の例を示す.
ユーザID
ユーザーが申告したID
説明:
"muzi"
"frodo"
「Muzi」は「Frodo」と報じた.
"apeach"
"frodo"
「apeach」は「frodo」と報じた.
"frodo"
"neo"
「frodo」は「neo」と報じた.
"muzi"
"neo"
「ミュー子」は「neo」を報告した.
"apeach"
"muzi"
「apeach」は「Muzi」を告発した
各ユーザーが通報された回数は以下の通りです.
ユーザID
通報回数
"muzi"
1
"frodo"
2
"apeach"
0
"neo"
2
上記の例では、2回以上通報された「frodo」と「neo」の掲示板は使用を停止します.この場合、ユーザーごとに申告したIDと無効なIDを以下のように整理することができます.
ユーザID
ユーザーが申告したID
停止したID
"muzi"
["frodo", "neo"]
["frodo", "neo"]
"frodo"
["neo"]
["neo"]
"apeach"
["muzi", "frodo"]
["frodo"]
"neo"
なし.
なし.
したがって、「muzi」には処理結果メールが2回、「frodo」と「apeach」にはそれぞれ処理結果メールが1回受信されます.
ユーザIDを含む文字列配列idリスト、ユーザごとに申告されたユーザID情報を含む文字列配列レポート、停止を基準とした申告回数kをパラメータとする場合は、ユーザごとに解決関数を1つ作成し、処理結果におけるメールの受信回数を列に記録して返してください.

I/O例

id_list
report
k
result
["muzi", "frodo", "apeach", "neo"]
["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"]
2
[2,1,1,0]
["con", "ryan"]
["ryan con", "ryan con", "ryan con", "ryan con"]
3
[0,0]

に答える

同じプレイヤーを1人のプレイヤーが繰り返し申告した場合、申告数は1回のみ有効となるため、重複したレポートの並びを消してから開始する.
["ryan con", "ryan con", "ryan con", "ryan con"] ➡️ ["ryan con"]

id listで各ユーザのインデックスを引き続き使用します.
申告数配列[0,0,0,0]とメール数配列[0,0,0,0]の順序はidリストの各ユーザの順序と同じである.

タイムアウトしたプール""""

まず,これはタイムアウトの最初の解法である.

デュアルリピートコード(マッピング)

function solution(id_list, report, k) {
  const newRepo = [...new Set(report)]; // report 중복 제거
  const out = []; // 정지 아이디
  const count = Array(id_list.length).fill(0); // 신고수 [0,0,0,0]
  const mail = Array(id_list.length).fill(0); // 메일수 [0,0,0,0]

  for (let r of newRepo) {
    let a = r.split(" ")[0]; // 유저 ID
    let b = r.split(" ")[1]; // 유저가 신고한 ID
    let idxB = id_list.indexOf(b); // id_list에서 신고받은 유저의 index 칮기
    count[idxB] += 1; // 신고받은 유저의 신고수 누적 더하기

    // 신고수가 k개 이상인 경우
    if (count[idxB] >= k) {
      // 정지 리스트에 해당 아아디 추가
      out.push(id_list[idxB])
    }
  }

  // 메일
  newRepo.map((r, idx) => {
    let a = r.split(' ')[0] // 유저 ID
    let b = r.split(' ')[1] // 유저가 신고한 ID

    // 이중반복문
    // 정지된 ID 배열의 반복문을 돌리면서
    for (let o of out) {
      // 유저가 신고한 ID(b)와 정지된 ID가 같을 때 찾기
      if (b === o) {
        let idx = id_list.indexOf(a);
        mail[idx] += 1;
      }
    }
  })

  return mail
}

繰り返し文は、プログラムのほとんどの実行時間を占めます.
コードの複雑さが最も高いところは重複文です.
上記コード「I/Oサンプル」のデータは問題ありませんが、コミット後にタイムアウトエラーが発生しました.
繰り返し文自体が入力するデータ量が大きいほど速度が遅くなり、繰り返し文の速度は当然倍になります.
二重複文を削除し,速度が改善された.

解決する

function solution(id_list, report, k) {
  const newRepo = [...new Set(report)]; // report 중복 제거
  const out = []; // 정지 아이디
  const count = Array(id_list.length).fill(0); // 신고수 [0,0,0,0]
  const mail = Array(id_list.length).fill(0); // 메일수 [0,0,0,0]

  for (let r of newRepo) {
    let a = r.split(" ")[0]; // 유저 ID
    let b = r.split(" ")[1]; // 유저가 신고한 ID
    let idxB = id_list.indexOf(b); // id_list에서 신고받은 유저의 index 칮기
    count[idxB] += 1; // 신고받은 유저의 신고수 누적 더하기

    // 신고수가 k개 이상인 경우
    if (count[idxB] >= k) {
      // 정지 리스트에 해당 아아디 추가
      out.push(id_list[idxB])
    }
  }

  // 메일
  newRepo.map((r, idx) => {
    let a = r.split(' ')[0] // 유저 ID
    let b = r.split(' ')[1] // 유저가 신고한 ID

    // 신고한 ID(b)에 정지된 ID가 있는지 확인
    if (out.indexOf(b) >= 0) {
      // 신고한 ID 중에 정지된 ID가 있다면, 
      // 해당 유저(a)의 id_list에서의 인덱스를 구하고
      // mail의 해당 인덱스에 1 더하기
      let idx = id_list.indexOf(a);
      mail[idx] += 1;
    } 

  }) 

  return mail
}

問題のソース
https://programmers.co.kr/learn/courses/30/lessons/92334