[프로그래머스] 입실 퇴실 / Javascript (위클리 챌린지 7주차)

문제주소 :https://programmers.co.kr/learn/courses/30/lessons/86048

코딩테스트 연습 - 7주차

 

---

<문제 설명>

문제 설명

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

오늘 회의실에는 총 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의 길이
  • 모든 사람의 번호가 중복없이 하나씩 들어있습니다.

---

입출력 예

enterleaveresult

[1,3,2]	[1,2,3]	[0,1,1]
[1,4,2,3]	[2,1,3,4]	[2,2,1,3]
[3,2,1]	[2,1,3]	[1,1,2]
[3,2,1]	[1,3,2]	[2,2,2]
[1,4,2,3]	[2,1,4,3]	[2,2,0,2]

---

입출력 예 설명

입출력 예 #1

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

회의실설명

[1]	1번 입실
[1, 3]	3번 입실
[3]	1번 퇴실
[2, 3]	2번 입실
[3]	2번 퇴실
[]	3번 퇴실

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

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

회의실설명

[1]	1번 입실
[]	1번 퇴실
[3]	3번 입실
[2, 3]	2번 입실
[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번은 만났는지 알 수 없습니다.

 

<풀이법>

▒ 한줄 개념: 큐 + 투 포인터 알고리즘 ▒ 

큐와 투 포인터 알고리즘을 사용하여 푼 문제입니다.

더욱 여러가지 방법이 있을 것도 같긴하나, 당장 떠오르는 방식대로 풀어냈습니다.

 

핵심 아이디어는 다음과 같습니다. 

우선 enter과 leave는 각각의 idx를 가지고 있고, 각 idx에 맞는 사람이 nextEnter, nextLeave(다음에 들어올, 나갈 사람)가 됩니다.

큐를 방이라고 가정하며, 조건에 따라 순서대로 삽입하게 됩니다. 

필수적으로 만나는 사람만 가정하는 것이므로, leave는 최대한 빨리 한다고 가정하여 조건을 설정하였습니다. 즉, leave가 enter보다 우선되는 것입니다. 

 

이를 표현한 조건은,

nextLeave가 queue에 있을 경우 pop 하면서, answer의 값을 증가시킵니다.

nextLeave가 queue에 없을 경우, nextEnter를 queue에 push해줍니다.

 

예시를 들어 설명해보겠습니다.

enter = [1, 4, 2, 3] / leave = [2, 1, 3, 4] 

 

queue = []
nextEnter = 1 (enter의 0번째)
nextLeave = 2 (leave의 0번째)
answer = [0, 0, 0, 0]

우선, queue에서 nextLeave를 바로 빼낼 수 있는지 확인해봅니다. 그러나 아직 queue에 nextLeave인 2번 손님이 들어가있지 않기 때문에, 빼낼 수 없습니다. 따라서 우선 들어가야 할 사람(nextEnter)를 먼저 방에 넣어줍니다.

 

queue = [1]
nextEnter = 4 (enter의 1번째)
nextLeave = 2 (leave의 0번째)
answer = [0, 0, 0, 0]

다시 nextLeave인 2번 손님을 빼낼 수 있는지 확인합니다. 그러나 역시 아직 2번 손님은 방에 들어간 적이 없습니다. 따라서 nextEnter를 다시 방에 넣어줍니다.

 

queue = [1, 4]
nextEnter = 2 (enter의 2번째)
nextLeave = 2 (leave의 0번째)
answer = [0, 0, 0, 0]

현재 방엔 1,4번 손님이 들어가있는 상태이고, 여전히 2번 손님(nextLeave)은 아직 들어가있지 않아 빼낼 수가 없습니다. 다음 손님을 또다시 방에 들여보내줍니다.

 

queue = [1, 4, 2]
nextEnter = 3 (enter의 3번째)
nextLeave = 2 (leave의 0번째)
answer = [0, 0, 0, 0]

 드디어 2번 손님(nextLeave)가 방에 들어갔네요! 이제 빼낼 수 있습니다! 최소 만남을 주선해야하므로, 얼른 빼내줍시다.

여기서 2번 손님을 빼내게 되면서 answer값 또한 update 해주게 되는데, 이 update 방식은 여러가지를 사용할 수 있을 것 같습니다. 

 저는 빼내는 사람은 남아있는 사람들 수만큼 더해주고, 남아있는 사람들은 1을 증가시켜주는 방식으로 구현하였습니다.

 answer[2] += queue.length; // 나오는 사람은 남아있는 사람 수 만큼 더하기

 answer[1]++; // 남아있는 사람은 나간 사람 한명만큼만 더하기

 answer[4]++; // 1과 마찬가지!

 

queue = [1, 4]
nextEnter = 3 (enter의 3번째)
nextLeave = 1 (leave의 1번째)
answer = [1, 2, 0, 1]

 2번 손님이 나가고, 다음 나갈 손님(nextLeave)는 1번 손님입니다. 누가 또 들어오기 전에 얼른 내보내줍니다. answer값이 증가하는 방식은 전과 같이, 나가는 1번 손님은 남아있는 손님들 수 만큼 더해주고, 남아있는 4번은 나간 사람 한 며만큼 더해줍니다.

 answer[1] += queue.length;

 answer[4]++;

 

queue = [4]
nextEnter = 3 (enter의 3번째)
nextLeave = 3 (leave의 2번째)
answer = [2, 2, 0, 2]

 다음 나갈 손님(nextLeave)는 3번 손님인데, 아직 3번 손님은 방(queue)에 들어가 있지 않습니다. 따라서 다음 들어갈 사람(nextEnter)를 들여보내 줍니다.

 

queue = [4, 3]
nextEnter = X
nextLeave = 3 (leave의 2번째)
answer = [2, 2, 0, 2]

 다음 나갈 손님(nextLeave)인 3번 손님이 방(queue)에 들어가 있으니, 얼른 내보내줍니다. 나가는 3번 손님의 answer 값은 방에 남아있는 손님만큼, 남아있는 손님은 나간 사람 한명만큼 값이 증가합니다.

 answer[3] += queue.length;

 answer[4]++;

 

queue = [4]
nextEnter = X
nextLeave = 4 (leave의 3번째)
answer = [2, 2, 1, 3]

 다음 나갈 손님(nextLeave)인 4번 손님이 이미 방(queue)에 들어가 계시네요. 잽싸게 내보내 드립니다. 이번 4번 손님이 나가는데 방에 남아있는 손님은 없으니, answer에는 0만 더해지겠네요.

 answer[4] += queue.length;

 

<코드(Javascript)>

function solution(enter, leave) {
    var answer = [];
    for(let i = 0; i < enter.length; i++){
        answer.push(0);
    }
    
    const queue = [];
    let eIdx = 0;
    let lIdx = 0;
    while(eIdx < enter.length || lIdx < leave.length){
        const nextLeave = leave[lIdx];
        const nextEnter = enter[eIdx];
        if(queue.indexOf(nextLeave) === -1){
            queue.push(nextEnter);
            eIdx++;
        }else{
            queue.splice(queue.indexOf(nextLeave), 1);
            if(queue.length){
                answer[nextLeave-1] += queue.length;
                queue.map(p => {
                    answer[p-1]++;
                })
            }
            lIdx++;
        }
    }
    
    return answer;
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest