Binary Search on Answer 도입으로 시간 복잡도 O(M*N)에서 O(log M * N)으로 최적화

Context

정수 x의 n제곱이 m이 되는 x를 찾는 Nth Root 문제 분석. 모든 정수를 순차적으로 검사하는 Brute Force 방식의 높은 시간 복잡도로 인한 비효율성 존재.

Technical Solution

• f(x) = xⁿ 함수의 Monotonic Increasing 특성을 활용한 탐색 범위 최적화
• Index 기반 탐색이 아닌 Answer Space [1, m]를 대상으로 Binary Search 적용
• Mid 값의 n제곱 연산 결과와 m을 비교하여 탐색 영역을 절반씩 제거하는 로직 설계
• 연산 중 Integer.MAX_VALUE 초과 시 즉시 반환하여 불필요한 계산 방지 및 Overflow 제어
• 정답 존재 여부에 따른 분기 처리로 -1 반환 조건 충족