백준 1269번인데

대칭차집합 문제임


대충 설명하면

집합 A,B가 있는데

대칭차집합 = A-B, B-A 의 합집합임

그래서 두집합의 합 sum

에서 중복되는원소 dup*2 를 빼주면 되는 문제인데


이 중복되는원소를 고를때

1. 집한 한개 정렬후 이분탐색

2. 둘다 정렬 후 반복자증가




(n>m인경우에)

위에께 O(nlogn) 정렬 + O(mlogn) 이분탐색 =72ms

밑에께 O(nlogn + mlogm) 정렬 + O(n+m) 탐색 = 68ms


둘중 위에께 더 좋은거아냐? 근데 왜 시간상으로는 밑의 방식이 좋다고 나오는지 모르겠음


그리고 이런문제들 이분탐색으로 전부 풀었는데

다른사람들꺼 보니까 밑에방식으로 전부 풀었더라고.

특정 조건만족시키면 

밑에처럼 반복자 증가시키는 방식으로 푸는게 더 좋은가?