2776번 : 암기왕

2776번: 암기왕

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며,

www.acmicpc.net

접근법

수첩 1에 적은 숫자들 저장
수첩 2에 적은 숫자들과 수첩 1에 적은 숫자들 비교
- find, count 함수등 있다, 없다를 판별하는 함수 사용
- 있다면 1, 없다면 0 출력

코드 1

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

int main() {
    int T;
    cin >> T;

    for (int t = 0; t < T; t++) {
        int n;
        cin >> n;
        vector<int> note1; //note1에 적힌 숫자들
        for (int i = 0; i < n; i++) {
            int num;
            cin >> num;
            note1.push_back(num);
        }

        int m;
        cin >> m; 
        vector<int> note2; //note2에 적힌 숫자들
        for (int i = 0; i < m; i++) {
            int num;
            cin >> num;
            note2.push_back(num);

        }

        for (int i = 0; i < m; i++) {
            if (count(note1.begin(), note1.end(), note2.at(i)) == 0) {
                cout << "0";
            }
            else {
                cout << "1";
            }
            cout << "\n";
        }
    }

    return 0;
}

시간초과 : 시간복잡도 O(T * m * n)

원인 : m,n이 커지게 되면 시간 복잡도 매우 증가하게됨

해결방안

해결 방법 : note1의 숫자를 벡터말고 set에 넣기, 이후 note2의 숫자를 찾기

set에 저장

set<int> note1; //벡터와 생성방법 동일

cin >> num; 
note1.intsert(num); //push_back 아닌 insert로 삽입

note2의 숫자 note1 set에서 숫자 찾기

cin >> note2_num; //note2의 숫자들 하나씩 입력
if(note1.find(note2_num) == note2_num.end()){
    //set에서 찾지 못한 경우 set의 end값을 반환함
     cout << "0";
else{
    cout << "1";
}

🔽 set으로 고쳤는데도 .. 시간초과 뜬다

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

int main() {
    int T;
    cin >> T;

    for (int t = 0; t < T; t++) {
        int n;
        cin >> n;
        set<int> note1; //note1에 적힌 숫자들
        for (int i = 0; i < n; i++) {
            int num;
            cin >> num;
            note1.insert(num);
        }

        int m;
        cin >> m; 

        for (int i = 0; i < m; i++) {
            int num;
            cin >> num;
            if (note1.find(num) == note1.end()) {
                //해당 원소가 없는 경우
                cout << "0";
            }
            else { //원소가 있는 경우
                cout << "1";
            }
            cout << "\n";
        }
    }

    return 0;
}

cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);

추가했더니 성공!!

전체코드

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

int main() {
    int T;
    cin >> T;

    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    for (int t = 0; t < T; t++) {
        int n;
        cin >> n;
        set<int> note1; //note1에 적힌 숫자들
        for (int i = 0; i < n; i++) {
            int num;
            cin >> num;
            note1.insert(num);
        }


        int m;
        cin >> m; 

        for (int i = 0; i < m; i++) {
            int num;
            cin >> num;
            if (note1.find(num) == note1.end()) {
                //해당 원소가 없는 경우
                cout << "0";
            }
            else { //원소가 있는 경우
                cout << "1";
            }
            cout << "\n";
        }
    }

    return 0;
}

저작자표시 (새창열림)