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

프로그래머스 나머지가 1이 되는 수 찾기를 C++로 풀어보겠다.

 

오래된 문제라 그런지 매우 쉽게 풀 수 있다.

 

다른 언어 풀이는 아래 링크를 참고하면 된다.

2022.08.23 - [Coding Test/Python] - [프로그래머스] 나머지가 1이 되는 수 찾기 Python Code

2022.08.23 - [Coding Test/Go] - [프로그래머스] 나머지가 1이 되는 수 찾기 Go Code

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

---

문제

---

구현

for문에서 2부터 n-1까지 돌면서 나머지가 1인지 확인하면 되는 쉬운 문제이다.

---

코드

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int solution(int n) {
    for(int i=2; i<sqrt(n); i++)
        if(n%i==1)
            return i;
    return n-1;
}

2부터 루트 n 까지 한 이유는

 

n이 3부터 시작하므로 2부터 검사해야 하고

 

소수 구하는 코드와 비슷한 로직인데

제곱근의 전까지 나누어지지 않았다면 그 이후는 다 나누어지지 않을 것이므로

바로 n-1을 리턴해주도록 했다.

---

다른 풀이

다른 풀이들처럼 전체를 다 검사하려면

아래 코드처럼 sqrt(n)을 없애도 현재 효율성 테스트가 없기에 통과할 수 있다.

#include <string>
#include <vector>
#include <cmath>
using namespace std;

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