ckdgus2482   7달 전

x에 대해서 정렬한 다음, 이분해서 해결하는 분할정복 알고리즘입니다.

좌측 부분문제와 우측 부분문제에서 구한 답을 비교하여 더 작은걸 minimum에 넣었습니다.

mlsIter는 분할된 좌측 부분에서 그것의 x좌표와 분할한 경계점의 x좌표 거리가 minimum 미만인 점들 중 x좌표가 가장 작은 점을 가리킵니다.

mreIter는 분할된 우측 부분에서 그것의 x좌표와 분할한 경계점의 x좌표 거리가 minimum 미만인 점들 중 x좌표가 가장 큰 점을 가리킵니다.

그상태에서 mlsIter부터 분할한 경계점 미만의 점들과 분할한 경계점부터 mreIter 미만의 점들과 1:1로 거리를 비교해서 가장 작은 거리를 찾고 이것과 minimum을 비교해서 더 작은 값을 리턴하도록 했습니다.

거리계산을 중복으로 하는 좌표쌍은 없는데 채점 93퍼쯤 가서 시간초과가 나네요.

알고리즘의 개선점이 있을까요? 아니면 코드수준에서의 최적화를 고려해야할까요?

ntopia   7달 전

x좌표만 신경쓰면

점들의 x좌표가 모두 같고 y좌표만 다른 경우에는

시간복잡도가  O(n^2) 이 되는 것 같습니다

appa   2달 전

게다가 멀티맵이라서 많이 느린 것 같습니다. 저도 x좌표 같은 게 많은 경우 TLE나야하는데 300ms로 통과했거든요....

댓글을 작성하려면 로그인해야 합니다.