6-G 게임을 map으로 시도했습니다

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

6-H

작성

298

안녕하세요 큰돌님.

이분탐색 대신 map을 활용해서 풀어봤는데 반례를 찾을 수가 없네요 ㅠㅠㅠ

어떤 부분이 잘못된건가요?

감사합니다.

#include <bits/stdc++.h>

using namespace std;


int T;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> T;
    while(T--){
        map<int, int> diary;
        int N, M, tmp;
        
        cin >> N;
        for(int i = 0 ; i < N ; i++){ cin >> tmp; diary[tmp]++;}
        
        cin >> M;
        for(int i = 0 ; i < M ; i++){
            cin >> tmp;
            diary[tmp]++;
            if(diary[tmp]>=2){
                cout << 1 << '\n';
                diary[tmp]--;
            }else{
                cout << 0 << '\n';
            }
            
        }
    }
    
    return 0;
}

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 태승님 ㅎㅎ

먼저 게임이 아니라 암기왕이겠죠? ㅎㅎ

일단 생각자체는 훌륭하고 좋습니다.

태승님이 생각하시는것은 아마 이런코드가 아닐까요? (조금 고쳐봤습니다. )

#include <bits/stdc++.h>

using namespace std;


int T;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> T;
    while(T--){
        map<int, int> diary;
        int N, M, tmp;
        
        cin >> N;
        for(int i = 0 ; i < N ; i++){ cin >> tmp; diary[tmp]++;}
        
        cin >> M;
        for(int i = 0 ; i < M ; i++){
            cin >> tmp; 
            if(diary[tmp] >= 1){
                cout << 1 << '\n'; 
            }else{
                cout << 0 << '\n';
            }
            
        }
    }
    
    return 0;
}

로직자체는 괜찮습니다.

나무랄데 없지요.

근데 이렇게 제출하면 시간초과가 뜹니다.

왜냐하면 map에다 집어넣게 되면 자동적으로 정렬이 들어가게 되는데 이 때문에 그런거 같아요.

즉,

        for(int i = 0 ; i < N ; i++){ cin >> tmp; diary[tmp]++;}

이 때마다 정렬하게 되고 N * O(logN)의 시간이 발생하니까 해답코드와는 그차이가 아닌가 싶습니다.

        for(int i = 0 ; i < M ; i++){
            cin >> tmp; 
            if(diary[tmp] >= 1){
                cout << 1 << '\n'; 
            }else{
                cout << 0 << '\n';
            }

물론 앞의 코드는 이분탐색과 동일한 시간복잡도를 갖는 코드구요.

감사합니다.

정태승

질문자

아 ㅠㅠ 죄송합니다 잘못적었네요 ㅋ쿠ㅜ

자동정렬로 시간복잡도가 차이가난 거였군요 !! 감사합니다!!

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

6-G 게임을 map으로 시도했습니다