[백준] 1269 대칭 차집합

▶ URL

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

 

▶ 문제

 

 

▶ 코드 및 리뷰

 

🅰️ 집합 A 처리

집합 A의 원소들을 읽어서 aset에 저장합니다. HashSet을 사용하여 중복을 허용하지 않았습니다.

 

---

🅱️ 집합 B 처리

집합 B의 원소를 하나씩 읽으면서 다음을 수행했습니다.

 

① 만약 집합 B의 원소가 이미 aset에 존재한다면, 이는 두 집합 A와 B에 공통된 원소라는 뜻이므로, aset에서 그 원소를 제거합니다.

이때 bset에는 값을 추가하지 않습니다. (이 과정에서 중복된 원소를 미리 제거하여 나중에 중복 계산을 방지합니다.)

 

② 만약 집합 B의 원소가 aset에 존재하지 않는다면, 이는 B 집합에만 속한 원소라는 의미이므로, count를 1 증가시킵니다.

 

---

 

🅰️ 집합 A에서 남은 원소들 처리

B의 모든 원소에 대해 처리한 후, 이제 aset에 남아있는 원소들은 A에만 속하는 원소들입니다. 이 원소들의 개수를 count에 더합니다.

 

---

최종 출력

count는 두 집합의 대칭 차집합의 원소 개수를 나타내며, 이를 출력하여 결과를 얻습니다.

 

 

아래는 혹시 풀어쓴(자세한) 풀이 방법이 필요할 수 있을 것 같아, 메모 형식으로 작성한 글이다!

aset

[1, 2, 4]

 

bset

1) 2를 입력 받을 때, aset에 2가 있으면 bset에 값을 넣지 않고 aset엔 값을 삭제한다.
삭제하는 이유? 겹치는 값은 count를 하지 않기 때문에 미리 삭제!
나중에 aset에서 bset과 겹치는 값을 계산할텐데 삭제를 안 하면 겹쳤던 그 개수만큼 계산을 할 것이라 미리 뺏다!

 

2) 3을 입력

Aset과 겹치는게 없다! 고로 count 1 증가

 

3) 4를 입력

Aset과 겹친다. Aset에 있는 4를 지우고 bset엔 해당 값을 넣지 않는다.

 

4) 5를 입력

Aset에 값이 없다. count 1증가

 

5) 6을 입력

aset에 값이 없다. count 1 증가

bset의 for문을 통해 count는 3이다!

 

 

이젠 aset로 가서 차집합 원소를 구해보자.

 

aset에 남아있는 값은 [1]일테다. 왜냐면 위의 과정에서 겹쳐지는 2, 4의 값은 삭제되었기 때문이다.

for문을 돌리는데 aset의 크기만큼 돌려준다.

그리고 bset과 중복되는 값이 있는지 확인하고 없다면 count값을 1 증가시킨다.

 

고로 1은 bset에 포함되어 있지 않기 때문에 count 1 증가시킨다.

 

따라서 정답은 4가 나온다! 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int count = 0; // 대칭 차집합의 원소 개수를 저장할 변수

        int a = Integer.parseInt(st.nextToken()); // 집합 A의 원소 개수
        int b = Integer.parseInt(st.nextToken()); // 집합 B의 원소 개수

        Set<Integer> aset = new HashSet<>(); // 집합 A를 저장할 HashSet
        Set<Integer> bset = new HashSet<>(); // 집합 B를 저장할 HashSet

        // 집합 A의 원소 입력 받기
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < a; i++) {
            aset.add(Integer.parseInt(st.nextToken()));
        }

        // 집합 B의 원소 입력 받기 및 처리
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < b; i++) {
            int num = Integer.parseInt(st.nextToken());

            // A에 있는 값이면 삭제, B에 추가하지 않음
            if(aset.contains(num)){
                aset.remove(num);
            }
            // A에 없는 값이면 카운트를 1 증가
            else{
                count ++;
            }
        }

        // A에 남은 원소의 개수를 count에 더함
        count += aset.size();

        // 최종 결과 출력
        System.out.println(count);
    }
}

 

 

 

세부 설명

 

중복 제거의 이유?

- aset에서 공통된 원소를 제거하는 이유는, 두 집합에 모두 속한 원소는 대칭 차집합에서 제외되기 때문입니다!

- 공통된 원소는 한 번만 제거되기 때문에 나중에 중복 계산이 발생하지 않습니다.

 

시간 복잡도?

- O(a + b)

- a는 집합 A의 크기, b는 집합 B의 크기입니다. HashSet을 사용함으로써 탐색 및 삭제가 평균적으로 O(1)에 수행됩니다.

 

 

 

 

 

오늘도 즐거운 코딩🌰

수정, 지적할 사항이 있다면 댓글로 알려주세요! 🐿️