lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read




문제 풀이

이번 문제는 집합과 맵 카테고리인만큼, HashMap을 활용한다면 손쉽게 풀 수 있다.
두 집합 A, B를 HashMap으로 받아서 서로의 중복원소를 카운트하면 대칭 차집합 원소 개수를 구할 수 있다.


아이디어 도출

  • 두개의 A와 B 집합을 HashMap으로 만든다. (key값은 입력값, value값은 0)
  • A에서 B를, B에서 A를 비교하여 중복원소를 카운트하여 value값을 카운트한다.
  • 대칭 차집합의 원소가 되는중복되지 않은 원소의 개수를 센다.


이제 코드를 작성해보자.

1
2
3
4
5
6
7
8

StringTokenizer st = new StringTokenizer(br.readLine());
int A_size = Integer.parseInt(st.nextToken());
int B_size = Integer.parseInt(st.nextToken());

HashMap<Integer, Integer> am = new HashMap<>();
HashMap<Integer, Integer> bm = new HashMap<>();

int cnt = 0;

A와 B 집합의 원소개수를 입력받고, 두 집합 각각을 HashMap으로 받기위해 두개의 HashMap을 선언하자.
그리고 대칭 차집합 원소의 개수를 담을 cnt 변수를 선언한다.

1
2
3
4
5
6
7
8
9
10

// A 집합 - HashMap
st = new StringTokenizer(br.readLine());
for(int i=0; i<A_size; i++ ) {
    am.put(Integer.parseInt(st.nextToken()), 0);
}
// B 집합 - HashMap
st = new StringTokenizer(br.readLine());
for(int i=0; i<B_size; i++) {
    bm.put(Integer.parseInt(st.nextToken()), 0);
}

공백을 기준으로 입력받은 A 원소와 B 원소를 각각 HashMap에 저장한다.
이 때 key값은 입력받은 원소 그대로 넣고, value값은 카운트를 세야하기에 0으로 넣는다.

1
2
3
4
5
6
7
8
9
10
11
12
13

// A-B
for(Map.Entry<Integer, Integer> A_entry : am.entrySet()) {
    if(bm.containsKey(A_entry.getKey())) am.put(A_entry.getKey(), 1);
    if(A_entry.getValue()==0) cnt++;
}

// B-A
for(Map.Entry<Integer, Integer> B_entry : bm.entrySet()) {
    if(am.containsKey(B_entry.getKey())) bm.put(B_entry.getKey(), 1);
    if(B_entry.getValue()==0) cnt++;
}

bw.write(cnt+"\n");

이제 대칭 차집합의 원소를 구하면 된다.

  1. A 집합에서 B 집합에서 중복되는 원소가 있는지 확인하여 카운트를 센다.
  2. 카운트가 올라가지 않았다면 중복되지 않아 대칭 차집합의 원소이므로 카운트가 0인 원소가 있다면 cnt를 1 증가시킨다.
  3. B 집합에서도 A 집합과 비교하여 위 과정을 반복하면 되고, 결국 대칭 차집합의 원소 개수 cnt를 출력하면 된다.



작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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

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 A_size = Integer.parseInt(st.nextToken());
        int B_size = Integer.parseInt(st.nextToken());

        HashMap<Integer, Integer> am = new HashMap<>();
        HashMap<Integer, Integer> bm = new HashMap<>();

        int cnt = 0;

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<A_size; i++ ) {
            am.put(Integer.parseInt(st.nextToken()), 0);
        }
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<B_size; i++) {
            bm.put(Integer.parseInt(st.nextToken()), 0);
        }

        // A-B
        for(Map.Entry<Integer, Integer> A_entry : am.entrySet()) {
            if(bm.containsKey(A_entry.getKey())) am.put(A_entry.getKey(), 1);
            if(A_entry.getValue()==0) cnt++;
        }

        // B-A
        for(Map.Entry<Integer, Integer> B_entry : bm.entrySet()) {
            if(am.containsKey(B_entry.getKey())) bm.put(B_entry.getKey(), 1);
            if(B_entry.getValue()==0) cnt++;
        }

        bw.write(cnt+"\n");

        bw.flush();
        bw.close();
        br.close();
    }   
}

회고

  • HashMap의 value값에 카운트를 세어두고 대칭 차집합의 원소가 되는지 검증하여 대칭 차집합의 원소개수를 구할 수 있었다.

You may also enjoy