[실버4] BOJ1269 대칭차집합

요구사항 정의

• 공집합이 아닌 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합의 원소의 개수를 출력하시오.
• 예시 : A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개
• 쉽게 말하면, 두 집합에서 중복되지 않은 값의 집합의 원소의 개수를 출력해라!

문제 분석

• 시간 제한 = 2초(2억번), 최대 N = 200,000
  → 최대로 안전하게 가능한 시간 복잡도는 O(N log N)
• A와 B를 비교할 때 A의 요소중 B 전체를 탐색하는 2중 for문은 안됨 → O(N^2)이기 때문
• 투 포인터로 두번의 for문만 돌면 가능할 듯? → A와 B 집합 → 2N = O(N)

손으로 풀기

• A 첫번째 요소, B 첫번째 요소에 투 포인터를 걸어둠
• 두 요소를 비교해 같지 않다면, count++ 하고 작은 값의 포인터++
• 두 요소가 같다면 count 하지 않고, 두개의 포인터 모두 ++
• 둘 중 한 집합의 포인터가 끝나면, 남은 집합의 요소의 개수만큼 count++

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1269_v2 {
    public static void main(String[] args) throws IOException {
        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());
        int A[] = new int[N];
        int B[] = new int[M];
        st = new StringTokenizer(br.readLine());
        for(int i =0;i<N;i++){
            A[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i =0;i<M;i++){
            B[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A);
        Arrays.sort(B);
        
        int A_index = 0;
        int B_index = 0;
        int count = 0;

        while(A_index < N && B_index < M) {
            if(A[A_index] < B[B_index]){
                count++;
                A_index++;
            }else if(B[B_index] < A[A_index]){
                count++;
                B_index++;
            }else {
                A_index++;
                B_index++;
            }

        }
        // 둘 중 남은 인덱스가 있다면 count에 증가시키기
        count += N - A_index; // A가 끝까지 안갔다면 남은 원소의 개수 -> 끝까지 갔다면 ex.3-3 = 0
        count += M - B_index; // B가 끝까지 안갔다면 남은 원소의 개수 -> ex예시코드 5-3 = 2
        System.out.println(count);
    }
}