6-H 질문있습니다 :)

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

6-H

해결된 질문

작성

수정됨

안녕하세요 선생님 🙂

6-H 문제를 보자마자 6-E 대칭 차집합 문제가 떠올라서 같은 방식으로 풀어봤는데요,

테스트케이스는 맞지만 틀렸다고 나옵니다. 이유가 뭔지 잘 모르겠어서 질문드립니다!!

http://boj.kr/0c301b3a0f1546d08e31a6b41e69ea70

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 유태님 ㅎㅎ

이거 시간초과 나오지 않나요?

그리고..

        vector<int> vecB(M);
        for (int i = 0; i < M; i++)
        {
            cin >> vecB[i];
        }

입력만 받아야 합니다. 굳이 mp에 넣을 필요는 없습니다. 해당 vecB를 기반으로 mp에 있냐 없냐를 확인하면 되기 때문입니다.

시간초과는 어떻게 해결할까요?

이문제는 시간이 타이트한 문제입니다. 이 경우 cin을 사용하지 않고 scanf 등을 사용하면 풀리기도 하는데요. 이렇게 하시면 됩니다.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int T;
int N, M;
map<int, int> mp;

int main()
{
    scanf("%d", &T);

    while (T--)
    {
        mp.clear(); 

        scanf("%d", &N);
        vector<int> vecA(N);
        for (int i = 0; i < N; i++)
        {
            scanf("%d", &vecA[i]);
            mp[vecA[i]] = 1;
        }

        scanf("%d", &M);
        vector<int> vecB(M);
        for (int i = 0; i < M; i++)
        {
            scanf("%d", &vecB[i]);
        }

        for (int i = 0; i < M; i++)
        {
            if (mp[vecB[i]] == 1) 
                printf("1\n");
            else 
                printf("0\n");
        }
    }

    return 0;
}

감사합니다.

한유태

질문자

시간초과는 나지 않지만 굉장히 타이트하네요;;

선생님 스타일 코드 체득해보겠습니다. 조언 감사합니다 선생님 :)

한유태

질문자

이 문제 다시 생각해보니, 기존 코드에서 mp[vecA[i]]++; 이 부분이 틀린 이유가 수첩1, 수첩2에 중복된 숫자가 입력된다면 문제가 생기는 코드였던 것 같습니다. mp[vecA[i]] = 1;로 하였으며, map을 undordered_map으로 변경하여 시간복잡도는 절반 이상 줄일 수 있었는데요, 공간복잡도가 선생님의 10배네요;; 절대로 좋은 코드가 아니었던 것 같습니다. 도움 감사합니다!

인프런 커뮤니티 질문&답변

6-H 질문있습니다 :)