5620번 - 가장 가까운 두 점의 거리
링크 달아주셔서 감사합니다.
두 글 다 읽었는데,
솔직히 구현할 방법이 조금도 떠오르지 않습니다.
글 작성자분이 올려주신 코드도 이해가 안가고,
두 글에서 공통적으로 X좌표, Y좌표를 정렬하고 거리를 미리 구해두고 컷을 하라는 것 같은데,
그걸 코드로 짜는게 조금도 생각이 나지 않습니다.
댓글 작성 알림 뜨자마자 지금까지 계속 봤는데, 도저히 이해가 안되네요.
이론조차 제대로 이해 못한 것이 맞습니다.
한시간 정도 계속 봐도 도저히 안들어와서 솔직히 포기했습니다.
당연히 이론이 안들어왔으니 구현도 할 수 없는 것 같습니다.
현재 제가 짠 코드 이외에 어떤 방법도 생각이 안납니다.
단순히 답만 찾기에는 문제가 없지만,
시간에 맞출 수 있도록 루프를 줄이는 방법은 글 두개를 다 봐도 모르겠습니다.
말씀하신대로 이론이 이해가 안되면 충분히 듣고 보며 이해를 해야겠지만,
그게 잘 안되네요. 코드를 짜는건 이론이 들어왔다면 계속 해보면 그만이라고 생각합니다.
최대한 잘 설명되어있는 것을 찾아보니, 해당 블로그를 보시면 좋을 것 같습니다.
https://mygumi.tistory.com/294
이 글과는 별개로, 제가 이해하는 라인-스위핑이란 방법을 정리해서 답변을 드리도록 하겠습니다.
원리는 생각보다 굉장히 쉽습니다.
현재의 최단거리를 D라고 했을 때, 중복되지 않는 점들에 대해서 D를 만족하는 최대 후보군의 수를 생각하면 6개밖에 되지 않습니다. (육각형의 각 꼭지점과 중앙점의 형태)
이를 확장해서, 직사각형의 형태로 풀어서 생각을 해보면 고작 8개밖에 나오지 않습니다. (중심점을 (x, y)라 했을 때 [x-d, x+d], [y-d, y+d] 구간으로 정사각형이 되는거죠.)
이 원리를 이용해서, 최단거리를 계속해서 갱신해주면서 후보군을 세어주는 알고리즘입니다.
[x-d, x+d]의 구간은 정렬을 해서 x가 증가하는 순으로 점들을 정렬해놓으면 쉽게 처리할 수 있습니다.
(현재의 점의 x좌표에서, x-d까지의 좌표들만 고려하면 되니까요. x점들은 정렬되어있으니 이진 탐색 등으로 해서 쉽게 찾을 수 있죠.)
[y-d, y+d]의 구간은 구간 안의 원소들을 순회할 수 있는 자료구조가 필요합니다. (우선순위큐나, 스택, 큐 같은 자료구조는 이를 성립하지 못하죠.)
적합한 자료구조로는 균형 이진 트리가 있습니다. (key값이 y값이면 되겠죠.)
삽입/삭제/탐색 시간은 O(logN)인 것을 잘 아실거라 생각합니다.
균형 이진 트리를 이용해서 [y-d, y+d]의 원소들을 순회해서 최단거리 d를 갱신할 수 있는지를 확인해주면 됩니다.
이 때 순회하는 원소의 수가 많을 것이라고 우려할 수 있으나, 위에서 체크한 것과 같이 최대 8개밖에 되지 않습니다.
(만약 8개보다 크다면, d값 갱신이 정상적으로 되지 않고 있는 것이죠.)
따라서 x축을 정렬하고O(NlogN), y축에 대해서 만족하는 원소들을 순회하는 과정(N * 8logN)으로 가장 가까운 두 점을 찾을 수 있습니다.
최종 시간복잡도는 O(NlogN)입니다.
이걸 기준으로 리스트 트리셋 두개, 리스트 두개로 정렬했는데, 이걸 어떻게 써먹어야 하나요..?
그리고
삽입/삭제/탐색 시간은 O(logN)인 것을 잘 아실거라 생각합니다.
이부분... 모릅니다.
이진 관련한것도 하나도 모르고, 시간 복잡도도 단계별 문제에서 달팽이 문제 풀 때 처음으로 질문 게시판에서 그런 용어가 있다는걸 접한게 다입니다.
올려주신 링크 글 보고 리스트를 만든게 다네요.
여기서 반복문을 돌리면 x랑 y의 사이즈가 다를거라 분명히 좌표값이 잘못 들어갈텐데,
어떻게 돌려야 하는건지 모르겠습니다.
감사합니다. 강해져서 돌아오겠습니다.
아무것도 모르는 초보 케어해주시느라 고생하셨습니다..ᅲᅲ
댓글을 작성하려면 로그인해야 합니다.
qorrhktk66 5년 전 0
시간 초과가 뜨는 것을 보니 반복문이 잘못됐거나, 반복문을 쓰면 안되는 것 같습니다.
그런데 아무리 생각해봐도 반복문을 안돌리면 거리를 비교할 수가 없는데...
어떻게 하면 시간을 줄일 수 있을까요?