사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다.
오늘 회의실에는 총 n명이 입실 후 퇴실했습니다. 편의상 사람들은 1부터 n까지 번호가 하나씩 붙어있으며, 두 번 이상 회의실에 들어온 사람은 없습니다. 이때, 각 사람별로 반드시 만난 사람은 몇 명인지 구하려 합니다.
예를 들어 입실 명부에 기재된 순서가 [1, 3, 2], 퇴실 명부에 기재된 순서가 [1, 2, 3]인 경우,
또 다른 예로 입실 순서가 [1, 4, 2, 3], 퇴실 순서가 [2, 1, 3, 4]인 경우,
회의실에 입실한 순서가 담긴 정수 배열 enter, 퇴실한 순서가 담긴 정수 배열 leave가 매개변수로 주어질 때, 각 사람별로 반드시 만난 사람은 몇 명인지 번호 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
입출력 예
입출력 예 설명
입출력 예 #1
만약, 다음과 같이 회의실에 입실, 퇴실했다면
만약, 다음과 같이 회의실에 입실, 퇴실했다면
위 방법 외에 다른 순서로 입실, 퇴실 할 경우 1번과 2번이 만나도록 할 수도 있습니다. 하지만 2번과 3번이 만나지 않도록 하는 방법은 없습니다.
따라서
입출력 예 #2
문제의 예시와 같습니다.
입출력 예 #3
입출력 예 #4
입출력 예 #5
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
하면 된다.