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

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

1822번: 차집합

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

 

 

 

 

 

문제

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.

출력

첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다. 집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.

예제 입력 1 복사

4 3
2 5 11 7
9 7 4

예제 출력 1 복사

3
2 5 11

 

 

 

 

<문제 풀이>

1. A, B를 입력받은 후 배열을 각각 선언한다.

2. 배열별로 값을 입력받아 저장한다.

3. for문을 통해 반복하며 A에는 있지만 B에는 없는 원소들을 따로 배열해 저장해둔다.

4. 총 개수와 원소들을 출력한다.

 

 

 

코드는 다음과 같다.

 

 

위의 코드는 c++ online compiler에서는 잘 돌아갔지만 백준 사이트에서는 '시간 초과'가 떴다.

뭔가 알고리즘의 시간복잡도 부분에 문제가 있는 것 같다. 

나중에 이 부분을 다시 공부하고 다시 시도해봐야겠다.