문제 푼 날짜 : 2021-11-01

문제

문제 링크 : https://www.acmicpc.net/problem/1822

접근 및 풀이

간단한 구현문제였다.
집합 A에는 있고, 집합 B에는 있지 않은 값들을 찾기 위해서 c++ algorithm 헤더에 있는 binary_search 함수를 이용하였다.
더 좋은 풀이가 존재할 것 같다.

코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int N, M, num;
    cin >> N >> M;
    
    vector<int> A(N), B(M), ret;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> B[i];
    }
    
    sort(B.begin(), B.end());
    for (int i = 0; i < N; i++) {
        if (!binary_search(B.begin(), B.end(), A[i])) {
            ret.push_back(A[i]);
        }
    }
    sort(ret.begin(), ret.end());
    cout << ret.size() << '\n';
    for (int i : ret) {
        cout << i << ' ';
    }
    return 0;
}

결과

피드백

vector의 find 함수로 구현하면 시간초과가 나는데, 이는 find 함수가 o(n)의 성능을 가지고 있어서 A, B 집합이 원소를 최대 500,000씩 가질 수 있기 때문에 충분히 그럴 수 있다.
이를 생각하지 못해서 첫 시도에 시간 초과가 뜨게 되었다.ㅠㅠ

바쁘단 핑계로 공부를 많이 못했다...
다시 차근차근 시작하자.