★Coordinate Compression Advanced - 2 Solved★

★ 18869 멀티버스 II ★

 

import sys
input=sys.stdin.readline
from collections import defaultdict

M,N=map(int,input().split())
cu_list,ans=[],0
def get_compressed_coordinate(l):
    sort_l = sorted(set(l))
    cd = {sort_l[i]: i for i in range(len(sort_l))}
    x = [cd[n] for n in l]
    return x

for _ in range(M):
    universe=list(map(int,input().split()))
    compressed_universe = get_compressed_coordinate(universe)
    cu_list.append(tuple(compressed_universe))

freq=defaultdict(int)

for cu in cu_list:
    freq[cu] += 1

for val in freq.values():
    if val > 1:
        ans+=(((val)*(val-1))//2)
print(ans)

 

🌎 균등한지 아닌지의 기준은 대소관계로만 판별하므로 크기 자체에 의미없고 크기 사이의 대소관계만 유의미하기에 Coordinate Compression 진행

 

🌎 입력받은 각 우주를 좌표 압축(get_compressed_coordinate)을 진행해서 각 우주에 존재하는, 크기에 따른 행성의 index 저장

ex) 1 3 2라면 각 행성의 좌표 압축 결과 index는 0 2 1 / 12 50 31이라면 좌표 압축 결과 index는 0 2 1

 

🌎 좌표 압축 결과 index를 tuple 형태로 cu_list에 넣음 → 빈도수 dictionary 저장 → 빈도수 2 이상일 경우만 쌍의 개수 누적 합 출력

---

★ 20440 🎵 니가 싫어 싫어 너무 싫어 오지 마 내게 찝쩍대지마🎵 - 1 ★

 

import sys
input=sys.stdin.readline
from collections import defaultdict

N=int(input())
delta_mosquito=defaultdict(int)

for _ in range(N):
    e,x=map(int,input().split())
    delta_mosquito[e] += 1
    delta_mosquito[x] -= 1

time=sorted(delta_mosquito.keys())

cumsum=[]
total=0
for i in range(len(time)):
    total+=delta_mosquito[time[i]]
    cumsum.append(total)
many=max(cumsum)
found=False
for x in range(len(cumsum)):
    if cumsum[x] == many:
        if not found:
            found=True
            s,e=x,x+1
        else:
            e+=1
    else:
        if found:
            break
print(many)
print(time[s],time[e])

 

🌎 BOJ 9574 <Goldilocks and the N Cows>와 비슷한 좌표 압축 문제

 

🌎 모기의 입장 / 퇴장 시간 숫자 자체는 중요치 않고 여러 모기의 입장 / 퇴장 시간 간의 대소 비교만 중요하므로 Coordinate Compression 유형

 

★ 핵심은 모기의 입장 / 퇴장 시간 수 범위가 2억이 넘어간다는 점 → 모기의 마릿수 N을 활용 ★

 

🌎

① hash map 생성: 모기의 입장/퇴장시간을 key, 해당 시간에 입장 + 1 / 퇴장 - 1을 활용한 모기 마릿수 변화량을 value

② hash map의 keys() 가져와서 오름차순 정렬

(입장/퇴장 시간 숫자 자체가 아닌 변화량만 따지므로 Coordinate Compression 기법 진행)

③ 정렬한 keys() for loop 돌리며 마릿수 변화량 누적합 list 생성 → 누적합 결과는 매 시간 모기의 마릿수

④ 즉 누적합 list의 최댓값 & 최댓값일 때의 start index / end index 구해서 출력

→ 가장 빠른 시각 기준 출력이므로 flag 값 활용하여 한 번 찾은 뒤 연속해서 최댓값이 아닌 경우만 제외 바로 break

---