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

작성한 질문수 7

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';
            }
            

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

감사합니다.