프로그래머스 위클리 챌린지 7주차 입실 퇴실 (C++)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/86048

코딩테스트 연습 - 7주차

문제 요약

 

1. 1번부터 n번까지의 사람들이 있습니다.

2. 1번부터 n번까지의 입실 / 퇴실 시간이 주어집니다.

3. 두 번 이상 입실하는 사람은 없으며, 입실과 퇴실이 동시에 이루어지는 경우도 없습니다.

4. 입실 시각과 퇴실 시각은 따로 기록하지 않습니다.

5. 1번부터 n번까지 각 사람이 반드시 만나게되는 사람의 수가 몇명인지 배열에 담아 출력하세요.

 

 

핵심 포인트

 

투 포인터로 접근할 수 있습니다.

풀이를 위한 핵심 로직은 다음과 같습니다.

• enter : [1,4,2,3]
• leave : [2,1,3,4]

1. 첫 번째로 방을 나가는 사람은 2번입니다.

room : [] // 방에 입장한 사람
나가는 사람 : 2

현재 방 안에는 아무도 없는 상태이므로, 사람을 1명 입장시킵니다.

 

2. 현재 방 안에는 다음과 같이 구성원이 존재합니다.

room : [1]
나가는 사람 : 2

아직 첫 번째로 방을 나가는 사람이 방에 들어오지 않았습니다.

다음 사람을 또 입장시킵니다.

 

3. 

room : [1,4]
나가는 사람 : 2

여전히 첫 번째로 방을 나가는 사람이 방에 들어오지 않았습니다.

다음 사람을 또 입장시킵니다.

 

4. 

room : [1,4,2]
나가는 사람 : 2

나가는 사람이 드디어 방에 들어왔습니다.

2번은 반드시 1,4번을 만나며, 나머지 사람들인 1,4번은 2번을 만나게 됩니다.

따라서 다음과 같이 만나는 사람의 수를 더해줍니다.

• 2번 : 방안에 있는 사람수 -1
• 1번, 4번 : +1 (2번을 만나는것이 확정이므로)

 

5. 나가는 사람을 방에서 제외해주고, 다음으로 방을 나가는 사람을 확인합니다.

room : [1,4]
나가는 사람 : 1

방안에 나가는 사람 1번이 존재합니다.

4번과 동일한 로직으로 만나는 사람 수를 더해줍니다.

• 1번 : 방안에 있는 사람수 -1
• 4번 : +1 (1번을 만나는게 확정이므로)

 

6. 나가는 사람을 다시 방에서 제외해주고, 또다시 다음으로 방을 나가는 사람을 확인합니다.

참고로 나가는 사람을 중심으로 만나는 사람을 계산해주는 것이므로, 투 포인터의 while문 조건은 나가는 사람의 값만 비교해줘도 충분합니다.

 

문제 풀이

 

위에 핵심에 세세한 설명이 적혀있으므로, 디테일한 설명을 제외합니다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> solution(vector<int> enter, vector<int> leave) {
    vector<int> answer(enter.size(),0);
    unordered_map<int,int> mp;
    int left=0,right=0,in=0,out=0;
    while(right<leave.size()){
        in = enter[left];
        out = leave[right];
        if(mp.find(out)==mp.end()){
            mp[in]++;
            left++;
        }else{
            answer[out-1] += mp.size()-1;
            mp.erase(out);
            for(auto i : mp) answer[i.first-1]++;
            right++;
        }
    }
    return answer;
}

 

 

 

테스트 1 〉	통과 (0.01ms, 4.27MB)
테스트 2 〉	통과 (0.01ms, 4.32MB)
테스트 3 〉	통과 (0.01ms, 4.26MB)
테스트 4 〉	통과 (0.02ms, 4.25MB)
테스트 5 〉	통과 (0.01ms, 4.26MB)
테스트 6 〉	통과 (0.03ms, 4.32MB)
테스트 7 〉	통과 (0.02ms, 4.27MB)
테스트 8 〉	통과 (0.03ms, 3.75MB)
테스트 9 〉	통과 (0.04ms, 4.25MB)
테스트 10 〉	통과 (0.12ms, 4.25MB)
테스트 11 〉	통과 (0.27ms, 4.26MB)
테스트 12 〉	통과 (0.39ms, 4.32MB)
테스트 13 〉	통과 (0.01ms, 4.27MB)
테스트 14 〉	통과 (0.01ms, 3.73MB)
테스트 15 〉	통과 (0.01ms, 4.33MB)
테스트 16 〉	통과 (0.01ms, 4.26MB)
테스트 17 〉	통과 (0.01ms, 4.25MB)
테스트 18 〉	통과 (0.01ms, 3.69MB)
테스트 19 〉	통과 (0.01ms, 3.66MB)
테스트 20 〉	통과 (0.01ms, 4.34MB)
테스트 21 〉	통과 (0.05ms, 4.27MB)
테스트 22 〉	통과 (0.05ms, 4.32MB)
테스트 23 〉	통과 (0.04ms, 4.27MB)
테스트 24 〉	통과 (0.36ms, 4.26MB)
테스트 25 〉	통과 (0.26ms, 4.25MB)
테스트 26 〉	통과 (1.20ms, 4.32MB)
테스트 27 〉	통과 (0.86ms, 4.02MB)
테스트 28 〉	통과 (0.01ms, 4.21MB)
테스트 29 〉	통과 (0.02ms, 4.31MB)
테스트 30 〉	통과 (0.04ms, 4.32MB)
테스트 31 〉	통과 (0.10ms, 4.26MB)
테스트 32 〉	통과 (0.27ms, 4.31MB)
테스트 33 〉	통과 (0.67ms, 4.25MB)
테스트 34 〉	통과 (0.69ms, 4.26MB)
테스트 35 〉	통과 (0.02ms, 4.27MB)
테스트 36 〉	통과 (0.03ms, 3.71MB)
테스트 37 〉	통과 (0.01ms, 4.32MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0