molla12   2년 전

푼 방법: 

C++의 atan2 함수를 이용해 한 점에 대한 다른 점들의 절대 각도(degree, [0, 360)°)를 구해 절대 각도들을 정렬한 후, 투 포인터를 이용해 직각삼각형의 개수를 세는 과정을 모든 점에 대해 반복했습니다.

절대 각도를 구할 때 처음 지정한 한 점일 경우에는 각도에 -1을 저장해 이를 건너뛰게 했고(정렬한 후 index 0을 건너뜀), 절대각도가 90°보다 작을 경우에는 360°을 더한 값을 각도 배열에 추가해 [270, 360)°의 각과 [0, 90)°의 각에 대해 직각삼각형인지를 올바르게 판단할 수 있도록 했습니다.

제가 푼 방법이나, 코드 구현 중 하나가 잘못되었을 것 같은데 잘 모르겠어서 질문 드립니다.

===============================

해결했습니다.

투 포인터를 사용하며 같은 값이 있을 때의 처리를 잘못했습니다. 

left(angle)의 같은 값이 a개, right(angle)의 같은 값이 b개이면 a + b - 1개(= 현재 처리한 방식: left, left + 1과 right, right + 1 중 각도 차가 적은 쪽의 index를 1만큼 증가시킴)이 아닌 a*b개로 수정해야 하기 때문에, 

각각의 angle을 map에 넣으며 count한 후 다시 배열에 저장해 투 포인터를 수행했습니다.

시간복잡도는 O(N^2logN)입니다.

수정한 코드

* 아래는 처음 질문할 때 올렸던 틀린 코드입니다.

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