문제

100/100
시간 : 좀 많이

간단정리

매개변수로 enter배열과 leave배열이있고
해당 배열은 들어오는 순서와 나가는 순서이고
이때 입실과 퇴실을 통해 적어도 만나는 경우에 배열값이 각각 증가한다.

접근

최악의 상황으로 고려를 했다.
누군가 입실을 하자마자 나갈만한 대상이 첫번째 배열값에 이미 있다면 그 대상을 내보내고 다음 배열값도 비교하고 (재귀)
비교를 못한다면
다음 입실자를 데려온다.

성공(제출)한 코드

function checkFirstLeave(room,leave){
    //제일 처음 퇴실한 대상이 해당 room 배열에 존재한다면 
    if(room.indexOf(leave[0]) >= 0 ){
            //해당 값을 room에서 제거 leave의 해당 값 또한 제거
            room.splice(room.indexOf(leave[0]) ,1)
            leave.shift()    
            
            //그다음 퇴실한 대상도 해당 room에 존재하나 재귀함수로 
            checkFirstLeave(room,leave)
    }

}

function solution(enter, leave) {
    const room = [];
    let obj = {};
    let count = 0;
    enter.forEach((num,idx)=>{
        // 1명씩 방에 입장
        room.push(num)
        
        const Room_Last_Value = room[room.length - 1]

        //해당 room안의 마지막으로 추가한 값과 남아있는 값들은 서로 만났으므로 +1을 한다.
        room.forEach(val=>{
            obj[val] = obj[val] ? obj[val]+1 : 1;
        })

        //해당 room안의 마지막으로 추가한 값은 배열만큼이 아닌 1번 밖에 더해지지 않았기 때문에 
        // 배열 전체에서 자기자신과 더한 1을 뺀 나머지 만큼을 추가해야한다. 
        // room의 길이가 4이면 3만큼이 추가되어야하는데 1은 이미 추가되므로 남은 2(4-2)만큼이 추가해야한다
        obj[Room_Last_Value] = obj[Room_Last_Value] + room.length - 2
        
        checkFirstLeave(room,leave,num)
    })
    
    let realAnswer = new Array(enter.length).fill(0)
    for (const [key, val] of Object.entries(obj)){
        realAnswer[key-1] = val;
    }
    return realAnswer
}

테스트케이스 34개중 2개가 오류였던 이유

new Array(enter.length)를 new Array(enter.length-1)로 해서
제대로된 배열 크기가 안만들어질 때도 있었던 것이다.

• new Array(value)의 value는 5라면 0~4까지의 5개의 배열값을 지닌 배열을 만들어 내는 것이다.

주요사항

재귀함수

function checkFirstLeave(room,leave){
    //제일 처음 퇴실한 대상이 해당 room 배열에 존재한다면 
    if(room.indexOf(leave[0]) >= 0 ){
            //해당 값을 room에서 제거 leave의 해당 값 또한 제거
            room.splice(room.indexOf(leave[0]) ,1)
            leave.shift()    
            
            //그다음 퇴실한 대상도 해당 room에 존재하나 재귀함수로 
            checkFirstLeave(room,leave)
    }

}

첫번째 배열값이 room에 존재하는 때까지 반복해서 재귀를 돈다.
(지금 생각한 건데 while로 해도 상관없지않을까?...)

최악의 상황으로 처리

누군가 입실하고 처음 나갈 대상이 있다면 무조건 내보내는 방향으로 처리

피드백

new Map()

new Map 예시1

key값의 조회 삭제 추가 할 경우 배열보다 쉽게 다룰수 있는 것 같다.

ex) 배열을 index찾고 splice하고 별짓 다하는것
=> new Map으로 hash값에 따라 delete 메소드 사용

const p = new Map();
p.set(5,true)
p.set(4,true)
p.set(3,true)
p.set(2,true)
p.set(1,true)
console.log(p)

p.forEach((person,i)=>{
  console.log(person,i)
})

for(const person of p){
  console.log(person)
}

for(const [person] of p){
  console.log(person)
}

true 5
true 4
true 3
true 2
true 1
[ 5, true ][ 4, true ]
[ 3, true ][ 2, true ]
[ 1, true ]
true
true
true
true
true

for of 로 new Map 순회도 가능하다

new Map 예시2

function checkFirstLeave(room,leave){
  //제일 처음 퇴실한 대상이 해당 room 배열에 존재한다면
  if(room.indexOf(leave[0]) >= 0 ){
    console.log(room,leave)
    //해당 값을 room에서 제거 leave의 해당 값 또한 제거
    room.splice(room.indexOf(leave[0]) ,1)
    leave.shift()
    //그다음 퇴실한 대상도 해당 room에 존재하나 재귀함수로
    checkFirstLeave(room,leave)
  }

}

function a(enter,leave){
  const room = []
  enter.forEach((person)=>{
    room.push(person)
    checkFirstLeave(room,leave)
  })
}

a([3,1,2],[1,2,3])

function b(enter,leave){
  const personInRoom = new Map()
  let leaveIdx = 0;
  enter.forEach((person)=>{
    personInRoom.set(person, true);
    while (personInRoom.get(leave[leaveIdx])) {
      console.log(personInRoom,leave)
      personInRoom.delete(leave[leaveIdx]);
      leaveIdx++;
    }
  })
}

b([3,1,2],[1,2,3])

a는 고유한 대상을 추가 삭제를 배열로 진행했고
b는 new Map으로 진행했다.
a보다 b의 장점은 a의 경우 퇴실을 확인하기 위해 O(n)으로 순회하고 있으나 b는 추가 삭제를 new Map을 통해 진행하여 O(1)로 효율성이 좋고 leave 또한 a는 shift를 통해 삭제를 진행하나 b는 leaveIdx를 통해 순차적으로 접근하고 있다.

다른 팀원의 코드

   
function solution(enter, leave) {
  const initialMeetCount = 0;
  const personMeetCount = Object.fromEntries(
    Array.from({ length: enter.length }, (e, i) => [i + 1, initialMeetCount])
  );
  const personInRoom = new Map();
  let leaveIdx = 0;
  enter.forEach((enterPerson) => {
    for (const [person] of personInRoom) {
      personMeetCount[person]++;
    }
    personMeetCount[enterPerson] += personInRoom.size;
    personInRoom.set(enterPerson, true);
    while (personInRoom.get(leave[leaveIdx])) {
      personInRoom.delete(leave[leaveIdx]);
      leaveIdx++;
    }
  });
  return Object.values(personMeetCount);
}

new Map을 잘 사용하였고
새로운사람이 출입전 기존 룸에 있는 사람들을 대상으로 for of를 하고
새로운사람을 기준으로 룸에 있는 인원들을 더하고
그 후에 새로운 사람을 추가했다.

new Map을 통해 배열로 순회하면서 splice하는 방법보단 효율성이 높다.

• 정리 : 고유한 key를 가진 대상의 추가삭제가 많으면 배열을 이용하여 indexOf splice 이용하지말고 new Map을 사용해봐라