[BOJ] 1822 - 차집합 (C++)

1. 문제

1822번: 차집합

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소

www.acmicpc.net

집합 A에는 속하지만, B에는 속하지 않는 원소들의 개수와 원소들을 모두 출력하는 문제이다.

집합에서 A - B (차집합)의 개념이 등장한다.

배열이나 리스트 등을 사용하면 해당 자료형 안에 특정 원소가 있는지 확인하려면 O(1)의 시간이 걸리기에,

접근하는데 시간이 O(1)이 걸리는 맵 자료형을 이용하여 문제를 해결했다.

먼저 A와 B 맵 두 개를 만들고 key 자리에 원소를 입력, value 자리에 1을 저장한다. (c++에서는 map에 key가 없어도 A[key] 형식으로 접근하면 value는 자동으로 0이 할당된다(int, int일시)

그렇게 A와 B에 각각 원소들을 저장하고,

iterator을 이용해

map<int, int>::iterator iter;

A의 map에 있는 모든 원소들을 돌면서 B에 있는지 확인한다.

확인하는 법은, B[iter->first] 값이 1인지 확인하면 된다. (find() 메소드를 이용했어도 가능했을 것이다; 앞에서도 얘기했듯이 map에서 key값이 없다면 0으로 value가 초기화됨)

지금 생각해보면 map이 아니라 set, 이진 트리/정렬 후 이진 탐색 등을 이용해 문제를 해결했어도 O(nlogn) 안에 문제를 해결할 수 있었을 것 같다. (set은 O(n))

+) 정렬과 이진 탐색을 이용해도 풀린다.

한 원소가 어떤 집합에 있는지 확인하려면

맵 : O(1)

이진트리/이진탐색 : O(logn)

웬만하면 이 두 가지 방법을 먼저 떠올리자.

// 맵을 이용한 코드

// 정렬과 이진 탐색을 이용한 코드

LIST