jhko00   3년 전

안녕하세요

라인 스위핑에 아직 익숙하지 않아 인터넷을 참고해 코드를 짜보았지만 시간 초과가 나서 질문드립니다

참고 사이트 주소는 https://wethinknewrise.tistory.com/m/6?category=845291입니다

위 사이트에서 x좌표 기준 범위 체크 후 y좌표 기준 범위 체크를 위한 정렬이 필요하다고 되어있는데

코드상으로는 정렬이 된 것 같지 않은 것이 문제로 보입니다

제 코드에 3줄 빈 주석 부분에 set을 y기준 정렬시키는 코드가 필요해보이는데

전체 반복문을 돌 때는 다시 x기준 정렬이 되어있어야 하는 것으로 보입니다 (while문의 else break부분)

라인 스위핑에 대해 잘못 이해한 것인지 질문드리고 이 방법이 맞는 경우 코드상으로 어느 부분이 문제인지 여쭤봅니다

slah007   3년 전

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좌표순으로 바꾸고 다시 생각해보세요.

herdson   3년 전

1. 배열은 x 기준 정렬, set은 y를 기준으로 정렬해야 합니다.

그래야 x를 스위핑하면서 후보가 될 수 없는 좌표를 걸러내고 y에 대해 스위핑하면서 최소 거리를 찾을 수 있습니다.

질문자님의 코드에서는 set에 대해 특별한 정렬기준을 제공하고 있지 않습니다. 그러면 set에 있는 좌표들도 x를 기준으로 정렬될 것이고 그 다음에 실행하는 bound도 제대로 작동하지 않을 가능성이 있는 것으로 보입니다.

2. bound 함수를 잘못 지정하셨습니다.

이 두가지 사항을 수정해서 제출해봄에도 불구하고 그럼에도 불구하고 시간초과가 나오길래 삼항 연산자로 연산하는 부분을 제거했더니 정답이 떴습니다.

제가 말씀드린 사항을 윗분이 올리신 튜토리얼을 참고해서 보완하면 정답을 받으실 수 있을 겁니다.

jhko00   3년 전

답글 주신 slah007님, herdson님 감사합니다

set에 y기준 정렬로 넣어주도록 해서 문제 해결했습니다

herdson님이 말씀하신 bound함수는 y==d일경우 무시해도 되기 때문에

y-d를 upper_bound, y+d를 lower_bound로 처리하였던 것이고

수정하지 않고 제출했어도 정답이 출력되는 것을 확인하였습니다

덕분에 라인 스위핑을 제대로 이해한 것 같네요

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