Diuven   2년 전

2261번 가장 가까운 점 찾기 문제에서, 지금 숏코딩 상위권들의 코드를 보면 x축으로 정렬 후 뒤의 점을 x값으로만 커팅하면서 보는데, 이러면 O(n^2)인 것으로 알고 있습니다.

근데 사실 이 문제에서는 이렇게 봐도 좌표제한이 걸려 있어서 최악의 경우에도 10000*10000*10~=10^9 정도 계산량으로 통과가 되는데, 원래 문제 의도가 이런건가요?

알고리즘 분류에는 라인 스위핑하고 분할정복이 있길래, 뭔가 이상해서 질문드립니다.




chogahui05   2년 전

저게 어떻게 통과하는지 의문이네요..

x축이 같고 y축이 전부 다른 데이터를 넣기만 해도 시간초과가 날 거 같네요.

Diuven   2년 전

사실 저도 그렇게 클레임을 넣으려고 했었는데, 좌표 절대값이 전부 10000이하라서, 10^5개 데이터를 어떻게 할 수가 없어요... 제가 생각했던 데이터는 x값 1차이나고 y값은 2차이나는, 지그재그로 점이 있는, 그런 데이터였는데 할려고보니 좌표 제한이 있더군요.

그래서 데이터를 최대한 집약시켜놔도 한 x값에 최대 10^4개정도, 그래서 적어도 10개 x값은 있어야되고, 인접한 x값끼리 전부 본다고 해도 10^9정도밖에 되질 않아요.


근데 방금 이런 데이터로 해보니 1.970 초가 나오네요. 이걸로도 충분하겠습니다.


데이터 추가 부탁드립니다!

startlink   2년 전

데이터를 추가했습니다.

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