백준/JAVA) 1269 대칭 차집합

대칭차집합

 

 

[Silver III] 대칭 차집합 - 1269

문제 링크

성능 요약

메모리: 81612 KB, 시간: 776 ms

분류

자료 구조(data_structures), 해시를 사용한 집합과 맵(hash_set), 트리를 사용한 집합과 맵(tree_set)

문제 설명

자연수를 원소로 갖는 공집합이 아닌 두 집합 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을 넘지 않는다.

출력

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

 

 

대칭차집합이란?

수학에서 '대칭차집합'이라고도 하는 두 집합의 '대칭차'란 한 집합에는 포함되지만,

두 집합 모두에는 포함되지 않는 원소들의 집합을 뜻한다.
자세한 설명 - Wikipedia

 

 

문제풀이

 

저번 '완주하지 못한 선수'라는 문제에서는 Python이 제공하는 모듈인 collections. 그 중 Counter라는 class를 이용했는데,

Counter class에서는 무려 배열 상호간 뺄샘연산을 지원한다.

JAVA에서도 두 집합(배열)간의 뺄샘연산을 지원한다면 좋겠지만..

찾아본 바로 JAVA에서는 Python의 Counter와 비슷한 class가 없어 조금 다른 방법을 사용하여 풀어보려고 한다.

 

일단 A집합의 크기와 B집합의 크기를 받아 각각 aSize와 bSize라는 int로 선언해준다

그리고 두번째 줄과 세번째 줄에 A/B 각 집합 내에 들어가는 원소들이 한 줄에 나열되어 주어지므로

원소들을 담을 HashSet을 선언해주었다.

 

먼저 A집합의 원소들은 처음 입력받았던 aSize만큼 반복하는 for문을 돌며

HashSet에 들어갈 수 있도록 코드를 작성했고,

 

그 다음 B집합의 원소들을 HashSet에 담을 땐 다음과 같은 방법을 이용하여 차집합을 구현할 것이다.

1. 만약 읽어온 숫자가 HashSet에 존재한다면 {HashSet에서 기존에 담았던 A집합의 원소를 제거한다}
   이유 : 겹치는 것들은 제거하면 곧 차집합이 되기 때문.
2. 만약 읽어온 숫자가 HashSet에 존재하지 않는다면 {HashSet에 읽어온 B의 원소를 넣어준다}

위와 같은 방법을 이용하면 간단하게 이번 '대칭차집합'문제를 해결할 수 있다.

 

Code

import java.io.*;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int aSize = Integer.parseInt(st.nextToken());
        int bSize = Integer.parseInt(st.nextToken());
        HashSet<Integer> set = new HashSet<>();
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < aSize; i++) {
            set.add(Integer.parseInt(st.nextToken()));
        }
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < bSize; i++) {
            int noDupNum = Integer.parseInt(st.nextToken());
            if (set.contains(noDupNum)) {
                set.remove(noDupNum);
            } else {
                set.add(noDupNum);
            }
        }
 
        bw.write(set.size());
        bw.newLine();
 
        bw.flush();
        br.close();
        bw.close();
    }
}

 

지나가다 본 건데, 백준 문제풀이를 할때 주의할 점으로는 자바의 Scaner 클래스를 이용하여 문제를 풀다보면

문제를 해결할 수 있는 코드라고 하더라도 시간초과로 실패하는 경우가 종종 있다고 한다.

그래서 입력을 받을 땐 입력받은 내용을 버퍼에 넣어두었다가 버퍼에서 읽어오는 BufferReader를 이용하고,

출력할땐 버퍼에 넣어둔 내용을 빠르게 읽어와 출력할 수 있는 BufferWriter를 이용하는 것을 습관화 하려고 한다.

StringTokenizer는 BufferReader를 통해 한 줄씩 읽어들인 내용을 하나씩 분리할 때 사용한다.

String을 Token화 한다는 이름처럼 지폐라고 볼 수 있는 line에서 동전이라고 할 수 있는 Token으로 분해하는 개념으로 일단 외워두려고 한다.

 

마지막에 bw.flush를 이용하여 버퍼를 비워주고 br과 bw를 모두 닫아주면서 코드를 마무리했다.

Buffer는 비워져있는 상태에서만 새로운 입력을 받을 수 있기때문에 비워주는 것이라고 한다.

 

위에서 BufferReader를 사용하며 aSize와 A집합의 원소들 등 에서 버퍼를 비우지 않은이유는 버퍼에 아무것도 남지 않도록

버퍼의 모든 데이터를 빼왔기 때문이다.

 

근데 인텔리제이에서 저거 세 줄 빼봤는데 잘 작동한다..ㅋㅋ

 

여담으로 백준에서 주 언어인 파이썬으로는 아직 문제를 풀지 못한게 원인인지..

괜히 보는사람 찜찜하게 '실패'로 뜬다........

하 나중에 파이썬으로도 풀어봐야겠다..

 

 

출처:

문제 : 문제 링크

대칭차집합 짤 : 대칭차집합 (수2) - NaverBlog