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한 후 다시 배열에 저장해 투 포인터를 수행했습니다.
molla12 2년 전 1
푼 방법:
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)입니다.
수정한 코드
* 아래는 처음 질문할 때 올렸던 틀린 코드입니다.