백준(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이 일치하는 구간이 존재하는지를 확인해야 하는데, 이는 그렇게 간단하게 구할 수 없기 때문에 이분 탐색을 사용했다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

D1={i:[] for i in range(1000001)}
D2={i:[] for i in range(1000001)}
for _ in range(int(input())):
    a,b=map(int,input().split())
    D1[a].append(b)
    D2[b].append(a)
for i in range(1000001):
    D1[i].sort()
    D2[i].sort()
for _ in range(int(input())):
    a,b=map(int,input().split())
    if not D1[a] or not D2[b]:
        print(-1)
        continue
    x=bisect.bisect_left(D1[a], b)
    y=bisect.bisect_left(D2[b], a)
    if bisect.bisect_right(D1[a],b)!=x and bisect.bisect_right(D2[b],a)!=y:
        print(1)
    elif D1[a][-1]>b and D2[b][0]<a:
        print(2)
    else:
        print(-1)

코포 스타일 문제라 코포 대비도 되는 느낌이었다.

시간 제한이 빡빡해 python으로는 시간 초과가 나서 pypy로 제출했다.