[알고리즘]BOJ_14569(시간표 짜기)

출처 : https://www.acmicpc.net/problem/14569

문제

연세대학교 수강신청 기간이 시작되었다. 많은 친구들은 비어 있는 시간에 어떤 과목을 추가로 신청할 수 있는지를 궁금해 한다.

이 친구들이 비어 있는 시간에 추가로 신청할 수 있는 과목의 후보 개수를 구해보자.

후보 개수를 세는 것이므로 현재 내 시간표에서 신청할 수 있는 과목끼리 시간이 겹치더라도 모두 세어야 한다.

즉, 월요일 1, 2, 3, 4, 5교시 시간이 비어 있고 한 과목의 시간이 월요일 1, 2, 3, 4교시이고 나머지 한 과목의 시간이 월요일 2, 3, 4, 5교시라면 2과목 모두 후보가 될 수 있다.

입력

연세대학교의 총 과목의 수 N (3 ≤ N ≤ 1000)이 주어진다.

N줄에 걸쳐서 각 과목의 수업시간의 수 k (4 ≤ k ≤ 50)가 주어지고 그 옆에 k개의 숫자 ti (1 ≤ ti ≤ 50)가 공백으로 구분되어 주어진다.

ti는 이 과목의 수업이 진행되는 교시를 의미하며 1 ~ 50의 값을 가진다.

(월요일 1~10교시: 1~10, 화요일 1~10교시: 11~20, …)

다음 줄에 학생수 M (1 ≤ M ≤ 10000) 이 주어진다.

M줄에 걸쳐서 각 학생들의 비어 있는 교시 개수 p (0 ≤ p ≤ 50)가 주어지고 그 옆에 p개의 숫자 qi (1 ≤ qi ≤ 50)가 공백으로 구분되어 주어진다.

Ex) 알고리즘의 수업시간이 화요일 2, 3교시, 수요일 4, 5교시라면 다음과 같이 입력이 주어진다.

4 12 13 24 25

출력

M줄에 걸쳐서 각 학생들의 들을 수 있는 과목 개수를 출력한다.

정답코드

#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

int main()
{
    FASTio;

    int n,m,p,tmp;


    vector<vector<int>> sub(n,vector<int> (0,0));

    for(int i=0; i<n; i++)
    {
        cin >> p;
        for(int j=0; j<p; j++)
        {
            cin >> tmp;
            sub[i].push_back(tmp);
        }
    }

    cin >> m;

    vector<bool> bin(51,false);

    while(m--)
    {
        for(int i=0; i<51; i++)
            bin[i]=false;

        cin >> p;

        for(int i=0; i<p; i++)
        {
            cin >> tmp;
            bin[tmp] = true;
        }
        
        int cnt = 0;

        for(int i=0; i<n; i++)
        {
            bool flag = false;
            for(int j=0; j<sub[i].size(); j++)
            {
                if(!bin[sub[i][j]])
                {
                    flag = true;
                    break;
                }
            }
            if(!flag) cnt++;
        }

        cout << cnt << endl;
    }

    return 0;
}

풀이 및 사고과정

일단 보기 좋게 1-50으로 시간을 표현한 것을 보니 강의 시간은 이차원벡터로 받고 빈 강의 시간은 크기가 51인(1-50이기때문)일차원벡터로 체크를 해서 풀면 될 것 같았다.

예를 들어 총 시간이 10까지 있고 빈 강의 시간이 1,2,3,10이라 가정하면
1,1,1,0,0,0,0,0,0,1로 마킹을 해놓고 강의 시간을 하나하나 대입해봐서 해당 강의 시간에 겹치는 인덱스가 모두 1이라면 cnt를 +1해주었다.

사고하기도 쉽고 코드작성도 어렵지 않았으나 어이없는 실수로 거의 1시간을 날려 먹었다.
바로 n을 입력 받기도 전에 vector<int> v(n)를 선언해서 쓰레기 값이 들어가버려 메모리초과를 초례했다.

이 문제가 발생했을 때 터미널에서 코드를 실행하면 원래 코드 돌아가는 속도보다 현저히 코드가 느리게 수행된다. 이 문제의 TC를 돌려보고 '이렇게 수행 시간이 긴 코드가 아닌데...'라고 생각했다. 그러고 1시간 뒤 예전에도 이와 비슷한 문제가 생겼었는데 왜 그랬을까 곰곰이 생각해봤는데 아니나다를까 n을 입력 받기도 전에 벡터를 선언한게 문제가 됐다.

이런 실수는 TC도 잘 통과해도 맞왜틀이 나오는 상황이다.
디버그를 해도 찾기 힘들고 시간도 오래걸려서 무조건 고쳐야할 습관인 것 같다.