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

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(vector<int> enter, vector<int> leave) {
    vector<int> answer;

    int enterNum = 0;   //들어올 사람 num
    int maxEnter = enter.size();    //인원 수

    vector<bool> entered(maxEnter, false);
    vector<set<int>> meet(maxEnter);  //만난 인원

    while (leave.size() != 0)
    {
        if (entered[leave[0] - 1] == true)  //입실 인원이 존재하면 퇴실
        {
            entered[leave[0] - 1] = false;
            leave.erase(leave.begin());
        }
        else if (enterNum < maxEnter)    //퇴실하지 않았다면 입실
        {
            for (int i = 0; i < maxEnter; i++)  //들어온 인원들은 현재 들어온 인원을 추가해준다.
            {
                if (entered[i] == true) 
                    meet[i].insert(enter[enterNum]);
            }

            for (int i = 0; i < maxEnter; i++) //새로들어온 사람은 들어와 있는 인원들을 추가해준다.
            {
                if (entered[i] == true) 
                    meet[enter[enterNum] - 1].insert(i + 1);
            }

            entered[enter[enterNum] - 1] = true;
            enterNum++; //입장num 증가
        }
    }

    for (int i = 0; i < maxEnter; i++) 
        answer.push_back(meet[i].size());


    return answer;
}

답안의 효율성

테스트 1 〉	통과 (0.02ms, 4.32MB)
테스트 2 〉	통과 (0.02ms, 4.09MB)
테스트 3 〉	통과 (0.02ms, 4.06MB)
테스트 4 〉	통과 (0.05ms, 4.28MB)
테스트 5 〉	통과 (0.02ms, 4.28MB)
테스트 6 〉	통과 (0.19ms, 4.26MB)
테스트 7 〉	통과 (0.09ms, 4.33MB)
테스트 8 〉	통과 (0.26ms, 3.79MB)
테스트 9 〉	통과 (0.46ms, 4.27MB)
테스트 10 〉	통과 (6.65ms, 5.9MB)
테스트 11 〉	통과 (25.88ms, 10.5MB)
테스트 12 〉	통과 (72.60ms, 16MB)
테스트 13 〉	통과 (0.01ms, 4.29MB)
테스트 14 〉	통과 (0.01ms, 4.28MB)
테스트 15 〉	통과 (0.01ms, 3.66MB)
테스트 16 〉	통과 (0.01ms, 4.22MB)
테스트 17 〉	통과 (0.02ms, 4.33MB)
테스트 18 〉	통과 (0.02ms, 4.28MB)
테스트 19 〉	통과 (0.02ms, 4.17MB)
테스트 20 〉	통과 (0.02ms, 3.67MB)
테스트 21 〉	통과 (0.83ms, 4.32MB)
테스트 22 〉	통과 (0.48ms, 4.25MB)
테스트 23 〉	통과 (0.16ms, 3.66MB)
테스트 24 〉	통과 (63.83ms, 13.6MB)
테스트 25 〉	통과 (19.25ms, 8.99MB)
테스트 26 〉	통과 (225.22ms, 43.8MB)
테스트 27 〉	통과 (179.21ms, 29.2MB)
테스트 28 〉	통과 (0.01ms, 4.2MB)
테스트 29 〉	통과 (0.02ms, 4.29MB)
테스트 30 〉	통과 (0.42ms, 4.27MB)
테스트 31 〉	통과 (2.76ms, 4.62MB)
테스트 32 〉	통과 (14.16ms, 8.15MB)
테스트 33 〉	통과 (66.43ms, 20.7MB)
테스트 34 〉	통과 (97.73ms, 21.1MB)
테스트 35 〉	통과 (0.02ms, 4.29MB)
테스트 36 〉	통과 (0.10ms, 4.26MB)
테스트 37 〉	통과 (0.01ms, 4.28MB)

 

 

풀이

1. 반드시 만나는 경우만 따지므로 최대한 퇴실을 바로바로 해준다.

2. 새로 들어오는 인원을 원래 있는 인원들에 추가해준다.

3. 새로 들어오는 인원은 현재 들어와있는 인원들을 추가해준다.

4. 퇴실 시에 현재 인원에서 퇴실처리하고, 퇴실인원에서 현재 퇴실하는 인원을 지워준다.

5. 만난 인원들을 답안에 넣어준다.

 

 

 

- 이전 답안 : 시간초과가 하나 나온다.. 효율을 생각 안하고 일단은 해봤는데 시간초과가 나왔다.

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(vector<int> enter, vector<int> leave) {
    vector<int> answer;

    int enterNum = 0;   //들어올 사람 num
    int maxEnter = enter.size();    //인원 수

    vector<bool> entered(maxEnter, false);
    vector<set<int>> meet(maxEnter);  //만난 인원

    while (leave.size() != 0)
    {
        if (entered[leave[0] - 1] == true)  //입실 인원이 존재하면 퇴실
        {
            for (int i = 0; i < maxEnter; i++)
            {
                if (entered[i] == true) //들어온 인원이라면
                {
                    for (int j = 0; j < maxEnter; j++)
                    {
                        if (entered[j] == true && i != j)   //들어온 인원들을 넣어준다.
                            meet[i].insert(j);
                    }
                }
            }

            entered[leave[0] - 1] = false;
            leave.erase(leave.begin());
        }
        else if (enterNum < maxEnter)    //퇴실하지 않았다면 입실
        {
            entered[enter[enterNum] - 1] = true;
            enterNum++; //입장num 증가
        }
    }

    for (int i = 0; i < maxEnter; i++) 
        answer.push_back(meet[i].size());


    return answer;
}

 

테스트 1 〉	통과 (0.02ms, 3.66MB)
테스트 2 〉	통과 (0.02ms, 3.67MB)
테스트 3 〉	통과 (0.02ms, 3.66MB)
테스트 4 〉	통과 (0.04ms, 4.26MB)
테스트 5 〉	통과 (0.03ms, 4.32MB)
테스트 6 〉	통과 (0.45ms, 4.27MB)
테스트 7 〉	통과 (0.24ms, 4.25MB)
테스트 8 〉	통과 (0.72ms, 4.32MB)
테스트 9 〉	통과 (2.20ms, 3.94MB)
테스트 10 〉	통과 (82.67ms, 6.07MB)
테스트 11 〉	통과 (553.29ms, 10.8MB)
테스트 12 〉	통과 (1659.97ms, 16MB)
테스트 13 〉	통과 (0.01ms, 4.32MB)
테스트 14 〉	통과 (0.01ms, 4.26MB)
테스트 15 〉	통과 (0.02ms, 4.33MB)
테스트 16 〉	통과 (0.02ms, 3.66MB)
테스트 17 〉	통과 (0.01ms, 4.25MB)
테스트 18 〉	통과 (0.03ms, 4.26MB)
테스트 19 〉	통과 (0.03ms, 4.32MB)
테스트 20 〉	통과 (0.02ms, 4.32MB)
테스트 21 〉	통과 (5.08ms, 4.25MB)
테스트 22 〉	통과 (1.78ms, 4.26MB)
테스트 23 〉	통과 (0.19ms, 4.27MB)
테스트 24 〉	통과 (1526.11ms, 13.4MB)
테스트 25 〉	통과 (572.69ms, 8.87MB)
테스트 26 〉	실패 (시간 초과)
테스트 27 〉	통과 (8121.94ms, 29.3MB)
테스트 28 〉	통과 (0.02ms, 4.32MB)
테스트 29 〉	통과 (0.03ms, 4.26MB)
테스트 30 〉	통과 (1.55ms, 4.32MB)
테스트 31 〉	통과 (22.26ms, 4.7MB)
테스트 32 〉	통과 (266.69ms, 8.12MB)
테스트 33 〉	통과 (2026.65ms, 20.7MB)
테스트 34 〉	통과 (2901.40ms, 21.3MB)
테스트 35 〉	통과 (0.02ms, 3.66MB)
테스트 36 〉	통과 (0.21ms, 4.27MB)
테스트 37 〉	통과 (0.01ms, 3.68MB)