[프로그래머스/JavaScript] 나머지가 1이 되는 수 찾기

 

이 문제를 처음 봤을 때는 굉장히 쉽다고 생각했습니다.

그저 for문을 돌려 나머지가 1이 되는 수를 찾으면 되니까... 너무 쉽잖아?라고 생각했는데요.

 

그러나 이제는 시간복잡도를 고려해 코드를 작성해야겠다는 생각에 조금 더 고민하는 시간을 갖게 되었습니다.

 

🤔 생각의 흐름

(1) n을 x로 나눈 나머지가 1이 되도록 하는 가장 자연수를 찾기 위해 n % x === 1을 꼭 사용해야 할까?
(2) 새로운 변수 m을 m = n - 1로 선언하고, 나머지가 0이 되는 가장 작은 자연수를 찾아보자.
(3) for문으로 전체를 돌린다면 시간복잡도는 O(n)이 될 텐데... 어떻게 하면 시간복잡도를 줄일 수 있을까?
(4) m이라는 수를 기준으로 중간 값, 혹은 제곱근 값 이하에서 찾으면 어떨까?

 

💻 결과 코드

function solution(n) {
    // answer : 결과
    let answer = 0;
    // m : 나머지가 1이 되도록 하는 가장 큰 자연수
    const m = n - 1;
    // sqrt : n - 1(m)의 제곱근
    const sqrt = Math.sqrt(m);
    
    // m의 가장 작은 약수 찾기
    for(let x = 2; x <= sqrt; x++) {
        if(m % x === 0) {
            answer = x;
            return answer;
        }
    }
    
    // m의 약수가 없을 경우
    answer = m;
    return answer;
}

 

GPT에게도 저의 코드가 괜찮은지 확인해봤습니다.

 

코드의 주요 부분은 for 루프로,
m의 가장 작은 약수를 찾기 위해 m의 제곱근까지 반복하고, 약수를 찾으면 해당 값을 반환합니다.

또한, 약수가 없는 경우에는 m 자체를 반환하도록 처리되어 있어 문제에 잘 부합하고,
시간 복잡도도 O(√n) 정도로 효율적입니다.

 

이 문제를 통해 쉬운 문제도 시간 복잡도를 고려해야겠다는 생각이 다시금 들었습니다.

다음 블로그 글도 기대해주세요 ⭐️