백준(boj)
[JAVA]18869 멀티버스2 , 좌표압축
📚 문제 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 🔍 아이디어 처음에는 그냥 기본적인 bruteforce풀이를 진행하였다. 골드 문제에 어울리지 않는다고 생각했는데 바로 시간초과가 났다. 이 풀이를 그대로 멀티버스 1번에 넣으니 통과되었다(브론즈 5) 못풀겠다 하고 침대에 누워있었는데 각 행성에 등수를 매기고 그 등수가 동일한 우주가 있다면 동일하게 균등하다고 할 수 있을 것 같다는 생각이 들었다. 그래서 싹 정렬을 하고 등수를 매겼다. 등수를 매길때 동일한 숫자는 동일한 등수를 주어야 하기 때문..
