[프로그래머스] 나머지가 1이 되는 수 찾기 자바 제곱근 활용

문제

주어진 n 을 나누어 나머지가 1이되게 하는 x 중 최소값을 구하라.

제한사항

3 ≤ n ≤ 1,000,000

접근

n이 100만까지 허용되므로, i = 2부터 n -1까지 단순작업을 하기엔 비효율적이라고 판단했다.
그러던 중 일전에 약수 목록을 구하는 문제 중 접했던 제곱근 방식에 착안하여 코딩하였다.

public static int solution(int n) {
        int answer = 0;

        //제곱근 방식으로 체크
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 1) {
                answer = i; //나머지 1인 x 중 제일 작은 값
                break;
            }
        }

        if(answer == 0) answer = n -1;

        return answer;
    }

 

제곱근 방식 (이전 예제)

List<Integer> divisors = new ArrayList<>();

for (int i = 1; i <= Math.sqrt(num); i++) {
    if (num % i == 0) {
        divisors.add(i);
        if (i != num / i) { // 중복 제거 (예: 5x3, 3x5)
            divisors.add(num / i);
        }
    }
}
Collections.sort(divisors); // 정렬 (옵션)