[Baekjoon] 1269번: 대칭 차집합

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

1269번: 대칭 차집합

문제 설명

두 집합 A, B가 주어질 때 ( A - B ) 와 ( B - A ) 의 합집합을 대칭 차집합이라고 한다. 이 대칭 차집합의 원소 개수를 구하면 된다.

풀이 방법 1. HashSet

집합이라는 문제에 걸맞게 HashSet으로 해결했다.

먼저 HashSet에 집합 A의 원소를 모두 넣는다. 그 다음 B의 원소를 넣을 때 이미 Set에 들어있다면 해당 요소를 제거하고 없다면 넣으면 된다. HashSet의 contains는 O(1)의 시간 복잡도를 가지기 때문에 아래 코드는 O(N) + O(2N)의 시간 복잡도로 계산된다.

Arrays.stream(br.readLine().split(" ")).forEach(s -> set.add(s));
Arrays.stream(br.readLine().split(" ")).forEach(s -> {
    if (set.contains(s))
        set.remove(s);
    else
        set.add(s);
});

전체 코드는 다음과 같다.

Java

package baekjoon.set;

import java.io.*;
import java.util.*;

public class BOJ1269 {

    static Set<String> set = new HashSet<>();

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            br.readLine();

            Arrays.stream(br.readLine().split(" ")).forEach(s -> set.add(s));
            Arrays.stream(br.readLine().split(" ")).forEach(s -> {
                if (set.contains(s))
                    set.remove(s);
                else
                    set.add(s);
            });

            System.out.print(set.size());
        }

    }
}

C++

#include <iostream>
#include <unordered_set>
#include <sstream>

using namespace std;

int n, m;
string arr1[200001], arr2[200001];
unordered_set<string> set;

int main()
{
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);

  cin >> n >> m;

  for (int i = 0; i < n; i++)
  {
    string str;
    cin >> str;
    set.insert(str);
  }

  for (int i = 0; i < m; i++)
  {
    string str;
    cin >> str;
    if (set.find(str) == set.end())
      set.insert(str);
    else
      set.erase(str);
  }

  cout << set.size();
}

풀이 방법 2. 정렬 후 이진 탐색 활용

다른 사람들의 C++ 해답을 확인해보다가 유난히 메모리와 시간이 적게 걸린 해답을 보게 되었고 솔직히 놀랐다.

이 방법의 알고리즘은 다음과 같다.

 

1. A 집합을 벡터에 입력받고 정렬한다.
2. B 집합을 입력받을 때 이진 탐색으로 벡터를 탐색한다. 만약 발견되면 카운트를 증가시킨다.
3. B 집합을 모두 입력받은 후 A 집합의 원소 개수 + B 집합의 원소 개수 - 중복이 발견된 카운트 * 2로 답을 계산한다.

곱하기 2를 하는 이유는 A 집합과 B 집합 모두에 들어있기 때문이다. 예를 들어 A = { 1, 2, 4 }, B = { 1, 2, 3, 5 } 라면 총 원소 개수는 7개이고 중복되는 원소는 1, 2로 두 개이다. 그렇기 때문에 { 1, 2, 1, 2, 3, 4, 5 } 인 총 개수에서 {1, 2} * 2 만큼 빼야 대칭 차집합을 구할 수 있다.

코드는 다음과 같다.

C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, m;
  cin >> n >> m;

  vector<int> arr(n);
  for (int i = 0; i < n; i++)
  {
    cin >> arr[i];
  }

  sort(arr.begin(), arr.end());

  int cnt = 0;
  for (int i = 0; i < m; i++)
  {
    int temp;
    cin >> temp;
    if (binary_search(arr.begin(), arr.end(), temp) == 1)
    {
      cnt++;
    }
  }

  cout << n + m - 2 * cnt;
}

Java

package baekjoon.set;

import java.io.*;
import java.util.*;

public class BOJ1269 {

    public static void main(String[] args) throws IOException {
        int N, M = 0;
        ArrayList<Integer> arr;
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] split = br.readLine().split(" ");
            N = Integer.parseInt(split[0]);
            M = Integer.parseInt(split[1]);

            arr = new ArrayList<>(N);
            Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                    .forEach(elem -> arr.add(elem));

            Collections.sort(arr);

            long cnt = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                    .filter(elem -> Collections.binarySearch(arr, elem) >= 0).count();

            System.out.print(N + M - cnt * 2);
        }
    }
}

자바의 경우 메모리는 줄었지만 시간은 오히려 늘어났다. Stream을 for 문으로도 변경해봤지만 유의미한 차이는 없었다.