본문 바로가기

728x90

정렬1

[백준] 18870. 좌표 압축/Python - Silver2 ❓문제https://www.acmicpc.net/problem/18870성능 요약메모리: 149248 KB, 시간: 1824 ms분류값 / 좌표 압축, 정렬 문제 설명수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.✍🏻풀이문제를 읽어보면 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수가 Xi'과 같다고 한다. 정말 단순하게 생각하면 이중반복문으로 풀 수 있다. 그러나 이 경우 시간 복잡도가 최악의 경우 O(N²)으로 N이 최대 1,000,.. 2025. 2. 19.

이전 1 다음

728x90

티스토리툴바