[알고리즘] 백준 > #1269. 대칭 차집합

자료구조를 써보자!

문제링크

백준 #1269. 대칭 차집합

풀이방법

간단한 문제이다. 값이 이미 존재하는 값인지 확인하고, 그렇다면 해당 값을 지우면 된다. 근데 여기서 사용하는 자료구조가 중요하다. 문제를 파악하면 다음과 같다.

배열 A, B 크기의 합을 n이라 하자.

• search: n번
• 삽입/삭제: n번

삽입/삭제에 비해 탐색연산을 더 많이 진행되는 것을 확인할 수 있다.

Java의 Collection에서 제공하는 List, Set, Map 중 어떤 인터페이스를 사용할지를 고민해보자. 일단 Map의 key, value 짝은 필요하지 않아서 제외하고 List의 LinkedList나 ArrayList의 경우 탐색에 유리하지 않다. Set의 TreeSet 구현은 Binary Search Tree 자료구조 형태를 가져 탐색에 유리하다는 장점이 있다. 이런 이유로 BST로 구현된 TreeSet을 이용해 문제를 해결했다.

코드

import java.util.Scanner;
import java.util.TreeSet;

public class SymmetricDifference {
    static Scanner sc = new Scanner(System.in);
    static TreeSet set = new TreeSet();
    public static void main(String[] args) {
        int numOfA = sc.nextInt();
        int numOfB = sc.nextInt();

        insertElements(numOfA);
        insertElements(numOfB);

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

    static void insertElements(int size) {
        for (int i = 0; i < size; i++) {
            int element = sc.nextInt();
            if (!set.add(element)) set.remove(element);
        }
    }
}