18870번 - 좌표 압축
시간초과가 뜨는데 어떤부분이 틀렸을까요. 프로그램 돌리면 예시는 올바른 정답이 나옵니다.
현재 로직은 시간복잡도가 O(N^2) 입니다.
N이 최대 1000000이므로 10^12번 정도 돌아가겠네요.
보통 10^8을 1초 정도로 잡고 계산하므로 시간초과가 맞습니다.
어떤부분이 틀렸다기보다는, 좀 더 효율적인 방법으로 구할 수 있게 로직을 생각해보셔요!
이 문제의 경우 약 O(NlogN) 정도의 시간복잡도를 가진 로직이 있습니다.
요청 카테고리는 관리자님이 처리하셔야 할 사항을 올리는 곳입니다. 질문은 질문 카테고리에 올려주세요.
댓글을 작성하려면 로그인해야 합니다.
wnscjf 4년 전
시간초과가 뜨는데 어떤부분이 틀렸을까요. 프로그램 돌리면 예시는 올바른 정답이 나옵니다.