백준 1269 대칭 차집합 자바 java

 

대칭 차집합을 구하는 문제이다.

 

문제에서 요구하는 것은 두 개의 집합 A, B가 있다고 할 때 A, B에 공통적으로 들어가는 값을 제외한

 

A, B의 값의 개수의 합을 구하는 것이다.

 

즉 겹치는 값의 개수를 구하면 간단하다.

 

해당 값이 존재하는지 알아보기 위해서는 contain함수를 활용하면 좋을 것 같다.\

 

우선 HashMap을 사용하여 풀어 보았다.

 

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        HashMap<Integer, String> map = new HashMap<>();
        HashMap<Integer, String> map2 = new HashMap<>();
        // 두 개의 HashMap를 사용하여 각각 값을 저장한 후 비교한다.

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

        for (int i = 0; i < N; i++) {
            map.put(i, st.nextToken());
        }
        // 첫 번째 집합의 값을 저장

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

        for (int i = 0; i < M; i++) {
            map2.put(i, st.nextToken());
        }
        // 두 번째 집합의 값을 저장

        int count = 0;
        //겹치는 값의 개수

        Set<String> valueSet = new HashSet<>(map2.values());
        // for-each문을 사용하기 위해 map2에 있는 value를 set으로 저장

        for (String value : valueSet) {
            if (map.containsValue(value)) {
                count++;
            }
            // 반복문을 통한 비교
        }

        System.out.print((N - count) + (M - count));

        br.close();

    }

}

 

 

하지만 HashMap을 사용하면 문제점이 있다. 

 

시간초과가 발생하는 것이다.

 

HashMap가 HashSet에 비해 연산시간이 오래걸리는 이유는 다음과 같다.

 

1. HashMap는 키-값을 저장하며 각요소에 대해 두 가지 정보가 필요하다. HashSet은 단순한 나열이다.

2. HashMap는 접근 시 키를 이용해야하지만 HashSet은 직접 접근이 가능하다.

 

이 두가지가 대표적이라고 할 수 있다.

 

간단히 말해 더 많은 정보를 복잡하게 활용하기 때문이다.

 

그래서 이번에는 HashSet를 사용해 보았다.

 

또한 두 개였던 HashMap을 한개의 HashSet로만 저장하고, 입력과 동시에 비교하도록 바꾸었다.

 

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        HashSet<String> set = new HashSet<>();

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

        for (int i = 0; i < N; i++) {
            set.add(st.nextToken());
            //HashSet에 값을 넣음
        }

        st = new StringTokenizer(br.readLine());
        int count = 0;
        // 겹치는 값을 저장하기 위한 count

        for (int i = 0; i < M; i++) {
        	// 두 번째 집합은 별도로 저장하지 않고 입력과 동시에 비교함
            
            if (set.contains(st.nextToken())) {
                count++;
                // 같은 값이 있을 경우 count++;
            }
        }

        System.out.print((N - count) + (M - count));
        //출력

        br.close();

    }

}