[백준] 1269 : 대칭 차집합

문제 출처: https://www.acmicpc.net/problem/1269

 

---

1. 문제

---

2. 시도

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

public class Main {
    
    private static final int range = 100_000_000;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());
        int[] arr1 = new int[n1];
        int[] arr2 = new int[n2];
        boolean[] check = new boolean[range + 1];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n1; i++) {
            int x = Integer.parseInt(st.nextToken());
            check[x] = true;
        }
        
        int cnt = 0;
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n2; i++) {
            int x = Integer.parseInt(st.nextToken());
            if(check[x]) cnt++;
        }
        
        System.out.print(arr1.length + arr2.length - 2 * cnt);
    }
}

 

무난하게 풀어서 520 ms 로 성공했다.

 

다른 사람의 풀이를 참고하니 개선할 점은 두 가지였다.

1. byte 단위 read() 함수를 직접 구현하여 실행 시간을 단축하기

2. 비록 boolean의 데이터 크기는 1 byte로 10 만 개의 boolean 배열을 만들어도 1 MB 밖에 소모되지 않지만 HashSet으로 불필요한 데이터 사용을 제거하기

 

1번은 여전히 이해하기 힘든 byte 단위 읽기 함수이기 때문에 자체적인 구현에 어려움이 있어 2번에 집중하기로 했다.

 

---

3. 풀이

 

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());
        HashSet<String> set = new HashSet<>();
        int cnt = 0;
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n1; i++) set.add(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n1; i++) {
        	if(set.contains(st.nextToken()) cnt++;
        }
        
        System.out.print(n1 + n2 - 2 * cnt);
    }
}

 

[ 수행 결과 ]

 

HashSet 을 적용했을 때, 기존과 근소한 차이를 보일 뿐 아니라 더 짧은 코드로 메모리를 절반이 소모되는 걸 확인했다.

---

4. 알게 된 점

 

 - 푸는 방법을 알아도 소요되는 메모리와 시간을 고려해야 하는 걸 파악한 문제였다.