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

2021. 9. 26. 22:21·Algorithm/Programmers
#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)

저작자표시 (새창열림)

'Algorithm > Programmers' 카테고리의 다른 글

[C++] 프로그래머스 큰 수 만들기 탐욕법  (0) 2021.10.12
[C++] 프로그래머스 위클리챌린지 8주차 최소직사각형  (0) 2021.09.30
[C++] 프로그래머스 위클리챌린지 6주차 복서정렬하기  (0) 2021.09.24
[C++] 프로그래머스 위클리챌린지 5주차 모음사전  (0) 2021.09.24
[C++] 프로그래머스 위클리챌린지 4주차 직업군추천하기  (0) 2021.09.24
'Algorithm/Programmers' 카테고리의 다른 글
  • [C++] 프로그래머스 큰 수 만들기 탐욕법
  • [C++] 프로그래머스 위클리챌린지 8주차 최소직사각형
  • [C++] 프로그래머스 위클리챌린지 6주차 복서정렬하기
  • [C++] 프로그래머스 위클리챌린지 5주차 모음사전
chanheess
chanheess
'왜' 그렇게 했는가?에 대한 생각으로 공부 및 작업의 저장관리
  • chanheess
    왜 그렇게 생각했는가?
    chanheess
  • 전체
    오늘
    어제
    • 분류 전체보기
      • Backend Programming
      • Game Programming
        • Unreal
        • DirectX
      • C++
        • Memo
        • Basic
        • Effective Modern
      • Java
      • Algorithm
        • Memo
        • Baekjoon
        • Programmers
        • HackerRank, LeetCode
      • Data Structure
      • Design Pattern
      • Etc
        • Memo
        • Daily Log
        • Book
  • 최근 글

  • 최근 댓글

  • 태그

    Java
    알고리즘
    위클리 챌린지
    프로그래머스
    dp
    JWT
    c++ 기초 플러스
    티스토리챌린지
    SpringSecurity
    spring
    JPA
    백준
    dfs
    오블완
  • hELLO· Designed By정상우.v4.10.0
chanheess
[C++] 프로그래머스 위클리챌린지 7주차 입실퇴실

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.