본문 바로가기
개발/알고리즘

[프로그래머스][LEVEL2] 입실 퇴실

by ISA(류) 2021. 9. 21.

# 문제 원문

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

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

입출력 예

enter / leave / result

[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]

 

# 문제 풀이

처음에는 조건문을 활용해서 경우의 수를 나누어서 카운팅할려고 했으나, 문제를 분석하다 보니 경우의 수가 생각 보다 많아서 조건문으로 처리하기에는 너무 복잡했다. 그래서 직접 입실 퇴실을 구현해서 각 사용자가 퇴실할때 마다 기존 인원들을 카운팅 하는 방향으로 반드시 접촉하는 접촉자들을 구했다.  회의실(state)에 들어와 있는 사람중 leave 큐 순서대로 나갈 수 있는 사람들이 있으면 내보내고 남은 접촉자들을 카운팅해준다. 입실 역시 enter 큐에서 한명씩 순서대로 입실한다.

 

# 솔루션 플로우

1. 입력 받은 enter와 leave 배열이 0 이 될때 까지 모든 요소를 반복한다.

2. 회의실(state) 배열에 현재 leave 큐 프론트 사용자가 있는지 확인한다.

3. 있을 경우 내보내면서 result를 카운팅한다. 해당 user이 나간후 회의실(state)에 남은 사람들 과 user에 각각 카운팅한다.

4. leave 큐 프론트의 사용자가 회의실에 없을때 까지 2~3 과정을 반복한다.

5. enter 큐 프론트에 사용자가 존재할 경우 회의실에 입실시킨다.

6. 위의 2-6 과정을 입력 받은 enter, leave 큐가 빌때까지 반복해서 result를 구한다.

7. 구해진 result를 반환한다.

1.반복문을 활용한 풀이

function solution(enter, leave) {
    const result = new Array(enter.length).fill(0);

    let state = [];
    while (enter.length > 0 || leave.length > 0) {
        while (state.includes(leave[0])) {
            state = state.filter((user) => user !== leave[0]);
            result[leave.shift() - 1] += state.length;
            state.forEach((user) => result[user - 1]++);
        }
        if (enter.length > 0) state.push(enter.shift());
    }

    return result;
}
반응형