백준 1269 대칭 차집합 문제 풀이
문제 파악하기
문제에서 제시한 두 개의 집합의 대칭 차집합의 원소의 개수를 구하는 간단한 문제입니다.
문제 풀어보기
각 집합의 원소의 개수가 200,000개까지 도달할 수 있음을 주목해야 합니다.
만약 입력을 그대로 배열로 전환한다면 검색 전략에 따라 다르겠지만, 어떤 값 N이 배열 안에 있는지 찾는 시간은 매우 오래 걸릴 것입니다.
시간 복잡도 O(logn)으로 알려진 이분 탐색을 도입하더라도 200,000, 200,000 크기의 집합이 두 쌍 주어진다면 시간 안에 통과를 장담할 수 없습니다.
따라서 어떤 값 N이 이미 입력으로 주어졌는지 “즉시” 확인할 수 있는 방법이 필요합니다.