[algorithm] 백준 1822 차집합

◾문제

차집합

레벨: 실버4

유형: 자료구조 / 정렬 / 해시를 사용한 집합과 맵 / 트리를 사용한 집합과 맵

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

 

 

 

◾풀이

TreeSet을 이용하여 풀이하였다.

문제이해

집합 A와 집합B가 주어질 때 집합 상 A - B인 차집합, 즉 A원소에서 B원소와 겹치는 부분을 제외한 부분을 구하는 문제이다. 아래와 같은 부분을 구하는 문제이다. 

 

 

TreeSet 사용하기

집합이므로 중복된 원소를 저장할 필요가 없으므로 Set을 이용하는 것을 생각하게 되었고, HashSet이 아닌 TreeSet을 사용하였다. 왜 TreeSet을 사용하였을까?

 

이유는 출력 조건에서 "구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다" 라고 하였기 때문이다. Set이라는 자료구조를 사용하되 정렬된 순서로 저장을 하고 싶다면 TreeSet을 이용할 수 있다. 

 

💡HashSet vs TreeSet
HashSet: 중복 허용X / 순서 X
TreeSet: 중복 허용 X / 정렬된 순서로 저장

TreeSet은 정렬된 순서로 저장하므로 출력할 때 정렬된 순서로 나오게 된다. 
Ex) 2,100,15 순서로 TreeSet에 저장한다. -> 2,15,100 순서로 저장된다.

 

 

 

차집합은 교집합을 제외한 것

집합 상 A-B를 구하는 것이므로 A집합에서 B집합과 겹치는 부분을 제외한 것만 구하면 된다. 그러므로 A원소를 입력받아 Set에 저장하고, B원소를 입력받으면서 A원소와 겹치는 부분만 A원소에서 제거하면 우리가 원하는 답을 얻을 수 있다.

 

처음에는 if문을 이용해 검사 후 제거해야 한다고 생각하였으나, 인텔리제이에서도 unnecesary 구문이라고 알려주었고 백준에도 if문 없이 통과가 되는 것으로 보아 굳이 넣지 않아도 되는 듯 하다.

       int bElement = Integer.parseInt(st.nextToken());
//     if (aSet.contains(bElement)) {
       aSet.remove(bElement);
//    }

 

 

 

 

◾정답코드

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

public class P1822 {
    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 aNum = Integer.parseInt(st.nextToken());
        int bNum = Integer.parseInt(st.nextToken());

        TreeSet<Integer> aSet = new TreeSet<>();

        st = new StringTokenizer(br.readLine());

        while (aNum-- > 0) {
            aSet.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        while (bNum-- > 0) {
            int bElement = Integer.parseInt(st.nextToken());
//            if (aSet.contains(bElement)) {
                aSet.remove(bElement);
//            }
        }
        bw.write(aSet.size()+"\n"); // 개수 출력

        Iterator<Integer> iter = aSet.iterator();
        while (iter.hasNext()) {
            bw.write(iter.next()+" ");
        }
        bw.flush();
        bw.close();
    }
}