[백준 2776번] 암기왕

https://www.acmicpc.net/problem/2776

2776번: 암기왕

 

📍 문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

 

📍 입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에  ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

 

---

📍 해결순서 및 주의사항

1. 수첩 1의 적어 놓은 정수의 개수와 수첩 2에 적어 놓의 개수가 모두 1,000,000이므로 많은 양의 수임을 인지해야 한다

2. 이는 두 개의 배열을 만들어서 둘을 비교하여 출력하면 된다고 생각함 → 이는 배열이 순서를 기억한다는 생각을 간과한 점!

3. 그으럼 수첩 1의 숫자를 적어놓을 배열을 만들어 놓고 숫자가 들어오면 그 해당 숫자의 배열을 1로 바꾸어 숫자가 들어옴을 표시함을 토대로 생각함

4. 하지만, 이를 더욱 효율적으로 활용할 수 있도록 map을 써보기로 함!! → map은 key+value 쌍으로 중복을 허용하지 않음!

 

 

#include <iostream>
#include <map>
using namespace std;

int main(){
   
    int T,N,M;
    int num; //노트1과 노트2에 넣을 숫자용
    cin>>T;
    for(int i=0;i<T;i++){
        cin>>N; //노트 1 정수 개수
        map<int,int> m; //해쉬 맵(key+value을 쌍으로 쓰는 map을 선택)
        for(int j=0;j<N;j++){
            cin>>num; 
            m[num]=1; //7이 들어오면 m[7]=1로 변하게 됨
        }
        cin>>M; //노트 2 정수 개수
        for(int j=0;j<M;j++){
            cin>>num;
            if(m[num]==1) //m[num]이 존재할 때(1일 때)
                cout<<"1\n";
            else //m[num]이 존재하지 않을 때(아무값이 아닐 때)
                cout<<"0\n";
        }
    }

    return 0;
}

그런데!!!!!!!문제 발생!!!!!!!

- > 시간 초과 발생ㅜㅜ

 

"1. 수첩 1의 적어 놓은 정수의 개수와 수첩 2에 적어 놓의 개수가 모두 1,000,000이므로 많은 양의 수임을 인지해야 한다"

     → 1번을 간과해서 생긴 문제인듯,,, 그럼 나는 cin,cout을 보통 쓰고 cstdio보다 iostream 형식을 많이 쓰게 되어서 발생하는 문제인 거 같다

     → 이럴 때에는 밑의 세줄을 int main() 다음에 바로 넣어주면 된다!!

ios_base::sync_with_stdio(false); //C의 stdio와 C++의 iostream의 동기화를 비활성화 한다 (즉, 평소엔 서로 동기화 상태)
cin.tie(NULL);
cout.tie(NULL);

첫번째 줄이 의미하는 바는 C의 stdio와 C++의 iostream의 동기화를 비활성화 한다 (즉, 평소엔 서로 동기화 상태)

두번째 줄이 의미하는 바는 원래 cout와 cin, 입출력은 묶여있다. 입력요청이 들어오면 그 전에 출력 작업이 있었을 경우(출력 버퍼에 내용이 있는 경우) 버퍼를 비워(flush) 출력하게 된다. 이 경우, 입출력이 반복될 때, 일일이 버퍼를 지우느라 시간이 오래 걸린다. 따라서, cin.tie(NULL) 을 통해 입출력 묶음을 풀면 시간이 단축된다.

 

#include <iostream>
#include <map>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); //C의 stdio와 C++의 iostream의 동기화를 비활성화 한다 (즉, 평소엔 서로 동기화 상태)
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T,N,M;
    int num; //노트1과 노트2에 넣을 숫자용
    cin>>T;
    for(int i=0;i<T;i++){
        cin>>N;
        map<int,int> m; //해쉬 맵(map을 선택)
        for(int j=0;j<N;j++){
            cin>>num;
            m[num]=1;
        }
        cin>>M;
        for(int j=0;j<M;j++){
            cin>>num;
            if(m[num]==1) //m[num]이 존재할 때(1일 때)
                cout<<"1\n";
            else //m[num]이 존재하지 않을 때(아무값이 아닐 때)
                cout<<"0\n";
        }
    }

    return 0;
}

 

 

📍 참고사항

https://velog.io/@gogori6565/BOJ-cin.tieNULL%EA%B3%BC-iosbasesyncwithstdiofalse

[BOJ/C++] cin.tie(NULL)과 ios_base::sync_with_stdio(false) 그리고 endl...

https://life-with-coding.tistory.com/305

[C++][STL] map 사용법 정리

https://blockdmask.tistory.com/87

[C++] map container 정리 및 사용법