[문제]

사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다.

오늘 회의실에는 총 n명이 입실 후 퇴실했습니다. 편의상 사람들은 1부터 n까지 번호가 하나씩 붙어있으며, 두 번 이상 회의실에 들어온 사람은 없습니다. 이때, 각 사람별로 반드시 만난 사람은 몇 명인지 구하려 합니다.

예를 들어 입실 명부에 기재된 순서가 [1, 3, 2], 퇴실 명부에 기재된 순서가 [1, 2, 3]인 경우,

• 1번과 2번은 만났는지 알 수 없습니다.
• 1번과 3번은 만났는지 알 수 없습니다.
• 2번과 3번은 반드시 만났습니다.

또 다른 예로 입실 순서가 [1, 4, 2, 3], 퇴실 순서가 [2, 1, 3, 4]인 경우,

• 1번과 2번은 반드시 만났습니다.
• 1번과 3번은 만났는지 알 수 없습니다.
• 1번과 4번은 반드시 만났습니다.
• 2번과 3번은 만났는지 알 수 없습니다.
• 2번과 4번은 반드시 만났습니다.
• 3번과 4번은 반드시 만났습니다.

회의실에 입실한 순서가 담긴 정수 배열 enter, 퇴실한 순서가 담긴 정수 배열 leave가 매개변수로 주어질 때, 각 사람별로 반드시 만난 사람은 몇 명인지 번호 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ enter의 길이 ≤ 1,000
• 1 ≤ enter의 원소 ≤ enter의 길이
• • 모든 사람의 번호가 중복없이 하나씩 들어있습니다.
• leave의 길이 = enter의 길이
• 1 ≤ leave의 원소 ≤ leave의 길이
• • 모든 사람의 번호가 중복없이 하나씩 들어있습니다.

입출력 예

입출력 예 설명
입출력 예 #1

만약, 다음과 같이 회의실에 입실, 퇴실했다면

• 1번과 2번은 만나지 않습니다.
• 1번과 3번은 만납니다
• 2번과 3번은 만납니다.

만약, 다음과 같이 회의실에 입실, 퇴실했다면

• 1번과 2번은 만나지 않습니다.
• 1번과 3번은 만나지 않습니다.
• 2번과 3번은 만납니다.

위 방법 외에 다른 순서로 입실, 퇴실 할 경우 1번과 2번이 만나도록 할 수도 있습니다. 하지만 2번과 3번이 만나지 않도록 하는 방법은 없습니다.

따라서

• 1번과 2번은 만났는지 알 수 없습니다.
• 1번과 3번은 만났는지 알 수 없습니다.
• 2번과 3번은 반드시 만났습니다.

입출력 예 #2

문제의 예시와 같습니다.

입출력 예 #3

• 1번과 2번은 만났는지 알 수 없습니다.
• 1번과 3번은 반드시 만났습니다.
• 2번과 3번은 반드시 만났습니다.

입출력 예 #4

• 1번과 2번은 반드시 만났습니다.
• 1번과 3번은 반드시 만났습니다.
• 2번과 3번은 반드시 만났습니다.

입출력 예 #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을 빼고 차례로 배열에 push해준다.

마지막으로 그 배열을 return하면 된다.