[백준 알고리즘] 1269번 : 대칭 차집합, c++

https://www.acmicpc.net/problem/1269

1269번: 대칭 차집합

c++로 백준 1269번 문제를 풀어보겠다.

 

 

 

 

 

문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.

예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때,  A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.

입력

첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.

출력

첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.

예제 입력 1 복사

3 5
1 2 4
2 3 4 5 6

예제 출력 1 복사

4

 

 

 

 

<문제 풀이>

 

처음에 작성한 코드는 다음과 같다.

'online c++ compiler'에서 실행할 때는 원하는 대로 실행됐지만, 백준 사이트에서는 '시간 초과'라고 떴다.

시간문제를 해결하기 위해 다른 방법을 사용해야 했다.

 

 

 

위의 문제를 해결하기 위해 100000000개의 bool형 배열을 사용했다.

 

1. A, B를 선언한 후 입력받는다.

2. n를 A번 입력받으며, 입력받을 때마다 bool형의 arrA배열 n번째의 값을 true(1)로 바꾼다.

3. n를 B번 입력받으며, 입력받을 때마다 bool형의 arrB배열 n번째의 값을 true(1)로 바꾼다.

(배열의 다른 값들은 모두 false(0)를 디폴트값으로 저장하고 있음)

4. 1부터 100000000까지 반복하며 배열 arrA와 arrB의 같은 위치에 저장된 값이 다르다면 count 값을 센다.

5. 최종적으로 계산한 count 값(대칭 차집합의 개수)을 출력한다.

 

 

 

최종 코드는 다음과 같다.