백준 1269 대칭 차집합

문제 출처: https://www.acmicpc.net/problem/1269

 

---

 

문제

문제

수학의 대칭 차집합 개념을 구현하는 문제이다.

 

문제에 제시된 예시를 읽어보면, 대칭 차집합에 대해선 간단하게 이해할 수 있을 것이다.

 

대칭 차집합이란?
 둘 중 한 집합에는 속하지만 둘 모두에는 속하지는 않는 원소들의 집합이다.

 

A = {1, 2, 4}
B = {2, 3, 4, 5, 6}

A - B = {1}
B - A = {3, 5, 6}

---

문제에서는 대칭 차집합의 결과로 남은 원소들의 갯수를 출력하는 문제이기 때문에 각 집합의 원소들을 출력할 필요는 없었다.

 

 

입출력 예제

 

입출력 예제

1 줄에는,

각 집합 (A , B) 의 원소의 갯수가 주어진다.

2 줄에는 A 집합의 원소가,

3 줄에는 B 집합의 원소가 주어진다.

 

각 입력값들은 빈칸을 두고 구분된다.

원소의 개수는 200,000 을 넘지않고, 모든 원소의 값은 100,000,000 을 넘지 않는다.

 

Main

문제의 핵심은 각 집합을 양방향 (A-B), (B-A) 으로 연산해야한다는 점이다.

 

우선, 사용자로부터 입력 값을 받고, 해당 입력값을 배열 안에 저장하고, 배열 안에 있는 값들을 하나씩 연산 하는 방법을 사용할 것이다.

 

아이디어 1

 

먼저, 각 집합의 요소 값들을 출력해야하는 것이 아니라, 각 집합 안에 있는 요소 갯수만 알아내면 되기 때문에, 

두 집합의 요소들 중 같은 요소가 있을 경우 cnt 라는 변수를 + 1 시켜주면서 

두 집합간에 같은 요소의 갯수만 각 집합의 요소 갯수에서 빼주면 후 각 나온 결과 값을 다시 더해주면, 두 집합의 대칭 차집합을 구할 수 있다. 아래는 아이디어 1 을 메모했던 페이지이다.

아이디어 1

아래는 아이디어 1 을 구현한 코드이다

 

import java.util.Scanner;

public class Bj1269 {

    public static void main(String[] args){ 

        // 백준 1269 대칭 차집합 문제
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        int [] a = new int[N];
        int [] b = new int[M];
        // 각 집합의 요소들을 저장할 집합 생성

        int cnt = 0;


        // 각 집합에 요소들 입력
        for (int i = 0; i<a.length; i++){
            a[i] =  sc.nextInt();
        }
        for (int j = 0; j<b.length; j++){
            b[j] = sc.nextInt();
        }

        for (int i=0; i<a.length; i++){
            for (int j = 0; j<b.length; j ++){
                if (a[i] == b[j]){
                    cnt++;
                }
            }
            
        }
        int n = N-cnt;
        int m = M-cnt;
        
        System.out.println(n + m);
        
        
        
    }

}

 

해당 코드를 통한 입출력값은 정답에 해당하긴 했다. 하지만 해당 결과를 백준에 제출해보니, 

백준 제출 결과

결과는 시간 초과였다. 

 

아마도 for 문의 차수와 갯수가 많아져, 연산이 오래 걸렸던 것 같다. 

---

 

아이디어2

 

문제와 관련해 다른 자료들을 찾아보니, 문제의 의도는 hashset 을 사용하는 것 같다. 

 

아래는 hashset 에 관련된 자료이다.

https://myeongju00.tistory.com/56

[Java] HashSet 정의 & 주요 메서드

 

Hashset 의 특징

1. 비선형 구조 (순서X)

2. 중복X

 

Hashset 선언

Hashset <데이터 타입> 변수이름 = new 데이터 타입 ();

 

hashset 을 사용하면 앞선 아이디어 1 에서 검색시간이 오래걸렸던 문제를 해결할 수 있다고 생각했다.

 

Hashset 을 사용해 문제를 해결하기 위해 코드를 다시 작성했다.

 

1. Hashset 안에 사용자로부터 입력받은 각 집합의 원소들을 저장한다.

2. 각 집합의 원소들을 비교하며 같은 원소가 있다면 cnt 변수 +1 한다.

3. cnt 값을 출력한다.

 

최종 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.HashSet;

public class Bj1269 {

    public static void main(String[] args) throws IOException{ 
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer (br.readLine());
        int cnt = 0;

        // A 집합과 B 집합의 크기 입력값 받기
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        // Hashset 선언
        HashSet<Integer> setA = new HashSet<Integer>();
        HashSet<Integer> setB = new HashSet<Integer>();

        // 각 집합의 크기만큼 입력값 받기
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<A; i++){
            setA.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<B; i++){
            setB.add(Integer.parseInt(st.nextToken()));
        }
        for (int num :setA){
            if (!setB.contains(num)){
                cnt ++;
            }
        }
        for (int num :setB){
            if (!setA.contains(num)){
                cnt ++;
            }
        }
        System.out.println(cnt);


    }

}