[JAVA] 백준 문제풀이(1269번 : 대칭 차집합)

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

1269번: 대칭 차집합

 

문제는 이렇다

 

우선 난 수포자급으로 수학은 잘 모른다.

 

고등학교때 기억나는게 좀 있긴한데 그닥 열성적으로 하진 않았음 ㅎㅎ ㅋㅋㅋ

 

공식이름 말하면 아 그거? 하는정도

 

아무튼 이번 문제 이름이 대칭 차집합 이라길래 차집합은 알겠는데 대칭 차집합은 뭔가 했었음

 

문제

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

출력

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

 

문제 내용을 보니 두 개의 집합이 있고 서로에 대한 차집합의 개수를 합하라는 것이 었음.

 

결국 두 집합에서 겹치는 원소를 제외하고 합친 길이를 구하라는 것이었기에 그렇게 어려운 문제는 아니였음

 

이걸 단순하게 배열로 구현해보려다가 문득 책에서 내용만 대강 보고 슥 지나간 Hash를 보고 써먹어보기로 했다.

 

 

솔직히 쓰는 방법을 잘몰라서 검색을 좀 해봤는데, 다른 메소드들과 크게 차이는 안나는듯.

 

 

package source;

import java.io.*;
import java.util.HashSet;
import java.util.StringTokenizer;

public class test_algo {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int sizeA = Integer.parseInt(st.nextToken()); //집합 A의 사이즈(길이)
		int sizeB = Integer.parseInt(st.nextToken()); //집합 B의 사이즈(길이)
		
		HashSet<Integer> hash = new HashSet<Integer>();
		//해쉬셋 선언
		
		StringTokenizer stA = new StringTokenizer(br.readLine());
		// 집합 A의 원소를 각각 분리
		
		for(int i =0;i<sizeA;i++) 
			hash.add(Integer.parseInt(stA.nextToken())); // A 집합의 길이만큼 반복하여 분리한 원소들을 add
		
		StringTokenizer stB = new StringTokenizer(br.readLine());
		// 집합 B의 원소를 각각 분리
		
		for(int i=0;i<sizeB;i++) {
			int elementB = Integer.parseInt(stB.nextToken());
			if(hash.contains(elementB))  //해쉬값에 해당 원소가 포함되어있다면
				hash.remove(elementB); //해당원소를 제거한다.
			else {
				hash.add(elementB); //포함되어있지 않다면 해당원소(B의 원소)를 넣는다.
			}
		}

		System.out.println(hash.size());
	
	}

}

 

1. 문제의 입력을 보면 공백과 줄바꿈으로 구분이 가능해서 한줄씩 읽고 공백으로 구분하는 방식을 택했다.

 

2. 첫번째 줄에 집합 A,B의 길이를 입력하기 때문에 StringTokenizer로 분리하여 첫번째 토큰은 A의 길이, 나머지 B의 길이

 

3. 해쉬를 써먹어야 하기 때문에 해쉬를 선언한다

 

4. A 집합의 분리한 원소들을 선언한 Hash에 넣어준다.(반복문으로 nextToken 삽입 반복)

 

5. 집합 B의 원소를 구분하고 넣는 과정에서

5-1. 해당 원소가 해쉬에 있는지 확인하는 contains

5-2. 만약 해당 원소가 해쉬에 존재한다면, 해당 원소를 해쉬에서 remove(제거)한다.

5-3. 해당 원소가 해쉬에 존재하지 않는다면 add

 

6. 5번의 과정을 통해 문제의 조건처럼 서로 겹치지 않는 원소들끼리 합집합을 구성했다.

 

7. 해쉬의 사이즈(길이)를 출력한다.

 

*StringTokenizer를 집합별로 계속 만들었는데, 어차피 한줄씩 읽어 오는 것이므로 같은 변수명을 사용하여 하는 것이 나음.

난 그냥 편의상 이해하기 쉽게 하기 위해 집합 별로 따로 선언했음