519-B, *1100

Problem - 519B - Codeforces

문제

• 크기가 $n(3 \leq n \leq 10^{5})$배열에서 원소가 2번 빠진다. 빠진 원소는?
• $O(nlog\ n)$ 알고리즘은 통과할 수 있다

 

$O(nlog n)$

배열 $a$에서 원소 하나를 빼면 배열 $b$가 된다고 하자
$a$ 와 $b$를 sort하고 $O(nlog\ n)$
앞부분부터 차례로 비교한다

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int n;
int a[100001] {};
int b[100001] {};
int c[100001] {};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n-1; i++) cin >> b[i];
    for(int i = 0; i < n-2; i++) cin >> c[i];
 
    sort(a, a+n);
    sort(b, b+n-1);
    sort(c, c+n-2);
 
    for(int i = 0; i < n; i++){
        if(a[i] != b[i]){
            cout << a[i] << endl;
            break;
        }
    }
 
    for(int i = 0; i < n-1; i++){
        if(b[i] != c[i]){
            cout << b[i] << endl;
            break;
        }
    }
    
    return 0;
}cs

 

$O(n)$

배열 $a$에서 원소 하나를 빼면 배열 $b$가 된다고 하자
$$\mathrm{Deleted\ element=Sum(a)-Sum(b)}$$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
 
int n;
ll a;
ll b;
ll c;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    int tmp;
 
    for(int i = 0; i < n; i++){
        cin >> tmp;
        a += tmp;
    }
 
    for(int i = 0; i < n-1; i++){
        cin >> tmp;
        b += tmp;
    }
 
    for(int i = 0; i < n-2; i++){
        cin >> tmp;
        c += tmp;
    }
 
    cout << a - b << endl << b - c << endl;
 
    return 0;
}cs