프로그래머스 위클리 7주차_입실 퇴실 cpp (구현)

문제 출처 : 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의 길이
  • 모든 사람의 번호가 중복없이 하나씩 들어있습니다.

---

입출력 예

입출력 예 설명

입출력 예 #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번은 만났는지 알 수 없습니다.

풀이

본인은 set을 이용해 풀었으며, 배열을 사용해도 상관없다.

풀이의 핵심은 i번과 j번이 반드시 만나는 경우만 카운트해야 하므로, 주어진 enter와 leave를 이용해, 가능한 서로 안 만나는 경우로 풀어나가야 한다.

최대한 사람을 안 만나게 하려면, 방에 있던 사람들 중, 본인이 퇴실을 할 수 있는 상황이면 바로 나가야 한다.

enter = [1,4,2,3]

leave = [2,1,3,4]

의 입력을 예로 들자.

room = [1]

answer = [0,0,0,0]

room에는 우선 1이 들어왔고, 먼저 들어와있던 사람이 없으니 카운트는 증가하지 않는다.

이 상태에서 1번은 나갈 수 있는가? 아니다 2번이 먼저 나가야 하므로 1은 아직 나갈 수 없기 때문에 다음 번호가 입실한다.

room = [1,4]

answer = [1,0,0,1]

이번엔 room에 4가 들어왔고, 먼저 들어와있던 사람 1과 4 모두 카운트를 증가한다.

이 상태에서도 2번이 먼저 나가야 하므로 1,4번 모두 아직 나갈 수 없기 때문에 다음 번호가 입실한다.

 

room = [1,4,2]

answer = [2,2,0,2]

이번엔 room에 2가 들어왔고, 먼저 들어와있던 사람이 1,4로 두 명이니 2번은 카운트를 두 번 증가하고, 1,4는 2를 새로 만났기 때문에 카운트를 한 번 증가한다.

이제 leave의 맨 앞에 있는 2가 나갈 수 있다.

그리고 퇴실을 할 수 있는 상황이면 바로바로 나가줘야 하기 때문에, 더 나갈 수 있는 사람이 있는지 체크하면

1이 나갈 수 있는 걸 알 수 있다. 따라서 room에서 2와 1이 나가고, 더 이상 나갈 수 있는 사람이 없으니 다음 번호가 입실한다.

 

room = [4,3]

answer = [2,2,1,3]

이번엔 room에 3이 들어왔고, 4와 3이 만났으니 둘 다 카운트를 증가한다.

leave에서 퇴실할 차례는 3번이고 3번 이후 4번도 나갈 수 있으니 모두 나가고 더 이상 입실할 사람이 없으니 프로그램을 종료한다.

 

 

코드

#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

vector<int> solution(vector<int> enter, vector<int> leave) {
    vector<int> answer(enter.size());
    unordered_set<int> se;
    int leaveIdx=0;
    int enterIdx=0;
    for(int i=0; i<enter.size();i++){
        //입장할 사람이 남아 있다면
        //cnt 증가
        answer[enter[i]-1]+=se.size();
        for(auto o : se){
            answer[o-1]++;
        }
        //입장
        se.insert(enter[i]);
        
        //퇴장할 사람이 방에 없을 때까지
        while(leaveIdx<leave.size() && se.find(leave[leaveIdx])!=se.end()){
            se.erase(leave[leaveIdx++]);
        }
    }
    return answer;
}