좌표 압축

[백준 BOJ / JAVA] 멀티버스 Ⅱ (18869번)

📘 1. 문제 소개 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 📘 2. 풀이 🧵 1. 좌표 압축 문제의 포인트는 좌표 압축이다. 좌표 압축이란 좌표 값들을 작은 범위의 값으로 압축하는 것이다. 수의 값에 상관없이 수의 대소관계만 알면 될 때 사용할 수 있다. -100, -4, 0, 3, 5000이라는 좌표가 있다고 해보자. 이를 배열처럼 표시한다면 다음과 같다. -100 ... -4 ... 0 ... 3 ... 5000 존재 존재 존재 존재 존재 하지만 압축을 이용하여 대소관계만 파악한다면 다음과 ..