プログラマコード問題2021、09/14-Lv.2入室チェックアウト


[質問]


社会的な距離を保つために、会議室に出入りするときは名簿に名前を書きます.入室とチェックアウトを同時に行う場合はなく、入室時間とチェックアウト時間は別に記録されません.
今日の会議室は全部でn人が入室してチェックアウトしました.便利な人は1からnまでそれぞれ番号があり、2回以上会議室に入ったことがない.この時、誰もが見たことがある人がどれだけいるかを明らかにしたいと思っています.
例えば、「入室名簿」の順序は[1,3,2]、「退室名簿」の順序は[1,2,3]である.
  • 1番と2番は会ったことがありますか?
  • 1日と3日は会った?
  • 2日と3日は必ず会わなければならない.
  • もう1つの例は、入室順が[1,4,2,3]、チェックアウト順が[2,1,3,4]の場合、
  • 1番と2番は必ず会わなければならない.
  • 1日と3日は会った?
  • 1日と4日は必ず会わなければならない.
  • 2日に3日に会いましたか?
  • 2日と4日は必ず会わなければならない.
  • 3日と4日は必ず会わなければならない.
  • 会議室で、入室順の整数配列enterと退室順の整数配列休暇をパラメータとする場合は、解法関数を完了し、一人一人が遭遇しなければならない人を番号順に配列に入れて返してください.
    せいげんじょうけん
  • 1≦enterの長さ≦1000
  • 1≦enterの要素≦enterの長さ
  • 各人の番号が一つで重複していない.
  • リーフの長さ=enterの長さ
  • 1≦葉の元素≦葉の長さ
  • 各人の番号が一つで重複していない.
  • I/O例

    I/O例説明
    I/O例#1
    このように会議室に入ってチェックアウトしたら
  • 1日と2日は会わない.
  • 1日と3日に会う
  • 2日と3日に会います.
  • このように会議室に入ってチェックアウトしたら
  • 1日と2日は会わない.
  • 1日と3日は会わない.
  • 2日と3日に会います.
  • 上記の方法のほか、他の順番で入室・チェックアウトすれば、1番と2番も会えます.しかし、2日と3日に会わせないわけにはいかない.
    したがって
  • 1番と2番は会ったことがありますか?
  • 1日と3日は会った?
  • 2日と3日は必ず会わなければならない.
  • I/O例#2
    問題の例.
    I/O例#3
  • 1番と2番は会ったことがありますか?
  • 1日と3日は必ず会わなければならない.
  • 2日と3日は必ず会わなければならない.
  • I/O例#4
  • 1番と2番は必ず会わなければならない.
  • 1日と3日は必ず会わなければならない.
  • 2日と3日は必ず会わなければならない.
  • I/O例#5
  • 1番と2番は必ず会わなければならない.
  • 1日と3日は会った?
  • 1日と4日は必ず会わなければならない.
  • 2日に3日に会いましたか?
  • 2日と4日は必ず会わなければならない.
  • 3日に4日に会いましたか?
  • [回答]

    function solution(enter, leave) {
      const answer = [];
      const map = new Map();		// 각 사람이 누구와 만났는지
      const room = new Set();		// 입실 상태
      const len = enter.length;		// 입실했던 총 인원
      let enterIdx = 0;
      let leaveIdx = 0;
    
      while((enterIdx < len) || (leaveIdx < len)) {
        // 입실자 명부를 확인하고, 퇴실자 명부에 현재 퇴실할 사람이 없을 때
        if(enterIdx < len && !room.has(leave[leaveIdx])) {
          room.add(enter[enterIdx]);
    
          map.set(enter[enterIdx], new Set([...room]));
    
          // 현재 방에 있는 사람들을 중복되지 않게 각각 set으로 관리
          for(let n of room) {
            map.get(n).add(enter[enterIdx]);
          }
    	
          enterIdx++;
        }
    	
        // 현재 퇴실자 명부에 leaveIdx가 가리키는 사람이 방에 있으면 
        if(room.has(leave[leaveIdx])) {
          room.delete(leave[leaveIdx]);
          leaveIdx++;
        }
      }
    
      for(let i = 1; i <= len; i++) {
        answer.push(map.get(i).size - 1);
      }
    
      return answer;
    }
    各人が誰と会うのか検索しやすいように利用しましたMap()入室者からチェックアウト者を削除しやすいように利用しましたSet().
    使用while入室者・チェックアウト者名簿を最初から最後まで繰り返し閲覧.
    まず前から入室者名簿を確認し、チェックアウトが必要な人がいなければ、誰もが部屋で誰と一緒にいたかの記録を更新し続けますMap例えば、チェックアウト者は考慮せず、仮に入居者のみが[1, 2, 3, 4, ...]起先1ひとり(1, [1])
    次に2入ってから、更新Map(1, [1, 2]), (2, [1, 2])
    次は3入ってまた更新Map(1, [1, 2, 3]), (2, [1, 2, 3]), (3, [1, 2, 3])
    入室者名簿を確認し、更新Map、そして前からチェックアウト者名簿を確認し、チェックアウトが必要な人が部屋にいる場合はroomからその人を減算します.
    このように繰り返していくと、一人一人が部屋にいるとき、一番多いときは誰と一緒にいるかを見つけることができます.
    1人1部屋のメンバーが自分を含めているので、自分が部屋で一番多い人数から外して1、順番に並んでpush最後にそれをreturnに並べばよい.