9015번 - 정사각형
우선 두 점을 잡아서 그 선분과 정사각형을 이룰 수 있는 네 점을 구합니다.
그 점들이 set에 저장되있는지 확인해서 최대크기 정사각형을 구하는 방법인데요
O(N^2 log(N))으로 풀었는데 시간초과가 나네요
시간을 줄일 수 있는 방법이 있을까요? 생각이 떠오르질 않네요
잡은 두 점의 선분의 길이가 지금까지 찾은 최대크기 정사각형의 한 변의 길이보다 짧으면 스킵하면 되지않을까요?
똑같이 시간초과네요
두 점의 선분을 저장한 뒤에 길이를 기준으로 내림차순으로 정렬한 후에
정사각형을 찾으면 탈출하는 방식도 해봤는데 이것도 마찬가집니다 ㅠㅠ
최악의 입력이 들어오면 결국 연산해야하니까 그런거 같아요
검사를 한번만하니까 통과되네요
전 set 대신에 unordered_map 써서 해결은 했는데요.
크기가 커서 아슬아슬하게 통과한 기억이 나네요.. 개인적으로 지뢰보단.. 뭐..
댓글을 작성하려면 로그인해야 합니다.
lyzqm 6년 전
우선 두 점을 잡아서 그 선분과 정사각형을 이룰 수 있는 네 점을 구합니다.
그 점들이 set에 저장되있는지 확인해서 최대크기 정사각형을 구하는 방법인데요
O(N^2 log(N))으로 풀었는데 시간초과가 나네요
시간을 줄일 수 있는 방법이 있을까요? 생각이 떠오르질 않네요