백준 1269 - 대칭 차집합(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1269

1269번: 대칭 차집합

map을 사용하는 문제입니다.

원소의 갯수가 200,000개 까지이기에 찾기 위해서 이중for문을 사용한다면 바로 시간초과가 생기는 문제입니다.

따라서, map을 사용해, 빠르게 찾는 방법을 사용해야합니다.

첫번째 수열과 두번째 수열을 입력 받은 뒤, 서로의 map에 저장해주고, for문을 통해 수열의 값이 다른 수열에 있는지 찾으면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <map>

using namespace std;

int N, M;
map<int, int> F;
map<int, int> S; 

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= N; i++){
		int x;
		cin >> x;
		F.insert({x, 1}); // 맵에 입력한다.
	}
	for(int i = 1; i <= M; i++){
		int x;
		cin >> x;
		S.insert({x, 1});
	}
	int cnt1 = 0, cnt2 = 0; // 첫번째 수열에만 있는 값의 갯수, 두번째 수열에만 있는 값의 갯수
	map<int, int> :: iterator i;
	for(i = F.begin(); i != F.end(); i++){
		if(S.find(i->first) == S.end()){ // 첫번째 수열에 있는 값이 두번째 수열에 없다면
			cnt1++;
		}
	}
	for(i = S.begin(); i != S.end(); i++){
		if(F.find(i->first) == F.end()){ // 두번째 수열에 있는 값이 첫번째 수열에 없다면
			cnt2++;	
		}
	}
	cout << cnt1 + cnt2;
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.