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

나머지가 1이 되는 수 찾기

문제 링크

나머지가 1이 되는 수 찾기

분석

문제 그대로 나머지가 1이 되도록 하는 가장 작은 자연수를 찾으면 됩니다.

이 문제는 브루트포스로 풀거나 n - 1의 약수를 확인해 푸는 방법이 있습니다.

풀이

브루프포스 방법으로 푸는 방법은 다음과 같습니다.

int solution(int n) {
    int answer = 0;
    
    for (int i = 2; i < n; ++i)
    {
        if (n % i == 1)
        {
            answer = i;
            break;
        }
    }
    
    return answer;
}

반복문을 사용해서 값을 순차적으로 확인합니다.
값을 찾았다면 반복문을 탈출하고 값을 반환합니다.

시간 복잡도는 $O(N)$입니다.

---

n - 1의 약수를 구해 푸는 방법은 다음과 같습니다.

#include <cmath>

int solution(int n) {
    int answer = 0;
    int target = n - 1;
    
    for (int i = 2; i <= std::sqrt(target); ++i)
    {
        if (target % i == 0)
        {
            answer = i;
            break;
        }
    }
    
    if (answer == 0)
    {
        answer = target;
    }
    
    return answer;
}

n을 나눌 때 나머지가 1인 값은 n - 1의 약수입니다.
그러므로 n - 1의 가장 작은 약수를 찾으면 됩니다.

만약 찾지 못했다면 target 변수가 소수이므로, 나머지가 1이 되도록 하는 가장 작은 자연수입니다.

시간 복잡도는 $O(\sqrt{N})$입니다.

성능 요약

브루프포스를 사용한 성능은 다음과 같습니다.

테스트 1 〉 통과 (2.26ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 3.62MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.14MB)
테스트 8 〉 통과 (0.01ms, 4.21MB)
테스트 9 〉 통과 (0.01ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 4.2MB)
테스트 11 〉 통과 (0.01ms, 3.73MB)

---

약수로 찾는 성능은 다음과 같습니다.

테스트 1 〉 통과 (0.01ms, 4.19MB)
테스트 2 〉 통과 (0.01ms, 4.12MB)
테스트 3 〉 통과 (0.01ms, 3.65MB)
테스트 4 〉 통과 (0.01ms, 4.2MB)
테스트 5 〉 통과 (0.01ms, 3.67MB)
테스트 6 〉 통과 (0.01ms, 4.14MB)
테스트 7 〉 통과 (0.01ms, 4.19MB)
테스트 8 〉 통과 (0.01ms, 4.13MB)
테스트 9 〉 통과 (0.01ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 4.2MB)
테스트 11 〉 통과 (0.01ms, 4.2MB)