https://www.acmicpc.net/blog/view/25
1. 전체 점들을 x가 증가하는 순으로 보면서
2. set에 넣을 때는 정렬기준을 y가 증가하는 순이라서 현재 점보다 왼쪽의(x좌표가 작은 것) 점 중 사용해야 할(y좌표 차이 d) 점을 O(log N) 만에 알 수 있는 것입니다.
일단 지금 코드에서는 위의 sort와 set의 정렬 기준의 차이가 없고 라인스위핑이 비효율적이라 O(n^2 log n)이 될 거 같아요. set의 정렬기준 자체를 y좌표순으로 바꾸고 다시 생각해보세요.
jhko00 3년 전
안녕하세요
라인 스위핑에 아직 익숙하지 않아 인터넷을 참고해 코드를 짜보았지만 시간 초과가 나서 질문드립니다
참고 사이트 주소는 https://wethinknewrise.tistory.com/m/6?category=845291입니다
위 사이트에서 x좌표 기준 범위 체크 후 y좌표 기준 범위 체크를 위한 정렬이 필요하다고 되어있는데
코드상으로는 정렬이 된 것 같지 않은 것이 문제로 보입니다
제 코드에 3줄 빈 주석 부분에 set을 y기준 정렬시키는 코드가 필요해보이는데
전체 반복문을 돌 때는 다시 x기준 정렬이 되어있어야 하는 것으로 보입니다 (while문의 else break부분)
라인 스위핑에 대해 잘못 이해한 것인지 질문드리고 이 방법이 맞는 경우 코드상으로 어느 부분이 문제인지 여쭤봅니다