시간복잡도를 줄이는 기술 2. 좌표압축

좌표 압축

• 탐색의 정점 번호가 1에서 10^9 사이 일 때 사용
• 주어진 정점 번호를 오름차순으로 나열한 뒤, 다시 1번부터 순서대로 매겨주며 범위를 줄이는 작업

아이디어

• 먼저 입력으로 들어온 모든 값(edges)을 treeset에 넣어줍니다.
• 작은 숫자부터 순서대로 뽑아, 각 숫자에 번호를 매기고 그 결과를 hashmap에 넣어줍니다.
• hashmap을 이용해 주어진 정점 번호를 1에서 N번 사이로 변경한다. (edges변경)

개념 코드

from sortedcontainers import SortedSet

edges = [
    (1, 10**9), (1, 2000), (1, 4), (30, 10**9), (6, 7)
]

nums = SortedSet()

# 사용되는 모든 번호를 treeset에 넣어줍니다.
for v1, v2 in edges:
    nums.add(v1)
    nums.add(v2)

# treeset에서 정점을 작은 번호부터 뽑으면서
# 각 정점별로 1번부터 순서대로 매칭하여
# 그 결과를 hashmap에 넣어줍니다.
mapper = dict()
cnt = 1
for num in nums:
    mapper[num] = cnt
    # 기존 정점번호마다 어떤 번호로
    # 정해졌는지를 출력해봅니다.
    print(num, "->", cnt)
    cnt += 1

# 주어진 간선을 이루는 정점 번호를
# 새로운 정점 번호로 변경해줍니다.
for i in range(5):
    v1, v2 = edges[i]
    edges[i] = (mapper[v1], mapper[v2])


>> 출력:
1 -> 1
4 -> 2
6 -> 3
7 -> 4
30 -> 5
2000 -> 6
1000000000 -> 7

 

문제 1. 수직선

수직선 상의 서로 다른 위치에 n개의 점에 주어졌을 때, q개의 질의에 대해 각각 구간 내 점의 개수를 출력

아이디어

arr 정렬 후 bisect을 이용하여 큰 index위치 (right) - 작은 index의 위치 (left) 로 개수를 판별한다. 

코드

#나의 풀이. 정렬한 뒤, bisect으로index찾은 후 사이 개수 구한다. 
n,q= map(int,input().split())
dots = list( map(int,input().split()))
dots.sort()
from bisect import bisect_right,bisect_left
for _ in range(q):
    a,b = map(int,input().split())
    print(bisect_right(dots,b)- bisect_left(dots,a))

 

문제 2. 평면

2차 평면 상의 서로 다른 위치에 n개의 점에 주어졌을 때, q개의 질의에 대해 각각 해당 직사각형 내 점의 개수를 출력

아이디어

평면 상의 X좌표로 범위를 줄이고, 해당 X좌표 구간안에 Y좌표를 탐색하며 정답을 찾으려함

1. x좌표만을 저장한 리스트 (sort)
2. x좌표를 key로 y좌표를 value로 한 dict 생성
3. from bisect import bisect_left,bisect_right 로 x좌표 구간을 (배열의 인덱스)를 얻고
4. 구간을 돌며 y좌표 조건 체크 , 속하면 cnt+1

코드

n,q=map(int,input().split())
dots=[]
mapper={}
for _ in range(n):
    a,b = map(int,input().split())
    dots.append(a)
    mapper[a]=b

dots.sort()
from bisect import bisect_left,bisect_right
for _ in range(q):
    x1,y1,x2,y2 = map(int,input().split())
    a=bisect_left(dots,x1)
    b=bisect_right(dots,x2)
    cnt=0
    for i in range(a,b):
        if y1 <= mapper[dots[i]] <=y2:
            cnt+=1
    print(cnt)