253931 백준(BOJ) 25393 교집합 만들기(Python) 이분 탐색 문제. 교집합은 반드시 1개 또는 2개의 구간에 의해서만 만들어지고, 이는 자명하다. 이때 교집합이 발생할 수 있는 경우는 l, r이 정확하게 일치하는 구간이 있는 경우 1개, l이 같고 r이 더 큰 구간과 r이 같고 l이 더 작은 구간이 동시에 존재하는 경우 2개. 위 두 가지의 경우에만 존재한다. 따라서 해시를 k를 l로 가지는 구간의 r의 집합과 k를 r로 가지는 구간의 l의 집합, 총 2개를 만들었다. 그 후에는 구간을 모두 해시에 저장하고, 두 해시 모두 k에 대한 값들을 정렬한다. 그 후에는 쿼리가 들어올 때마다 위 경우를 판단해주면 되는데, 이때 구간이 2개인 경우에는 크게 문제가 없지만, 구간이 1개인 경우에는 문제가 발생한다. 정확하게 l과 r이 일치하는 구간이 존재하는지를 확.. 2023. 1. 13. 이전 1 다음