[Programmers] 위클리 챌린지 7

안녕하세요. 이번 포스팅에서는 위클리 챌린지 7 입실 퇴실에 대한 포스팅을 진행해 보겠습니다.

 

https://programmers.co.kr/learn/courses/30/lessons/86048

코딩테스트 연습 - 7주차

 

해당 문제는 위 링크에서 확인하실 수 있습니다.

 

생각보다 처음 조건을 찾는 것에 애를 먹은 문제입니다.

 

enter : [1, 3, 2]

leave : [1, 2, 3] 

 

위의 예시를 한번 살펴보면,

 

3이 2보다 먼저 들어왔고, 2보다 늦게 나갔기 때문에 2와 3은 필연적으로 만날 수밖에 없습니다.

 

추가적인 예시로

 

enter : [1, 4, 2, 3]

leave : [2, 1, 3, 4]

 

를 보면, 

 

2는 1과 4를 만날 수 밖에 없습니다.

1은 2와 4를 만날 수 밖에 없습니다.

3은 4와 만날 수 밖에 없습니다.

4는 모두와 만날 수 밖에 없습니다.

 

 

한번 추가 예시를 살펴보겠습니다.

 

2가 처음으로 나갔을 때 방에 1과 4가 존재합니다. 따라서 1, 2, 4는 서로 만날 수밖에 없습니다.

 

2가 나간 뒤, 1이 나갔습니다. 그렇게 되면 방에는 4만 남거나, 3이 들어와서 3과 4가 있을 수 있습니다. 하지만 특정할 수 없습니다. 

 

1이 나간 뒤, 3이 나갔습니다. 현재 방에 4가 있는 것이 자명하므로, 3과 4는 만날 수 밖에 없습니다.

 

 

즉, 이 문제를 해결하려면, leave를 우선적으로 처리하면서, 현재 필연적으로 방에 남아있을 수밖에 없는 인원들만 count 해주면 됩니다.

 

저의 경우는 방문 배열을 하나 선언해서, 이미 처리된(방을 떠난) 사람들에 대해 방문 처리를 해 주었습니다. 

또한, 매번 사람이 나갈 때 마다 나간 사람이 enter 배열에서 몇 번 째인지 파악해서, 방에 필연적으로 남아있을 수밖에 없는 사람을 세어 주었습니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> enter, vector<int> leave) {
    vector<int> answer(enter.size()+1, 0), visited(enter.size()+1, 0);
    
    int checkRange = 0;
    for(int i = 0; i < leave.size(); i++) {
        int cur = leave[i];
        visited[cur] = 1;
        
        int idx = (int)(find(enter.begin(), enter.end(), cur) - enter.begin());
        checkRange = max(checkRange, idx);
        for(int j = 0; j < checkRange; j++) {
            if(!visited[enter[j]]) {
                answer[cur]++;
                answer[enter[j]]++;
            }
        }
    }
    
    answer.erase(answer.begin());
    return answer;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.