[프로그래머스] 스킬체크 레벨1 - 나머지가 1이 되는 수 찾기

문제 설명

자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다.

---

제한사항

• 3 ≤ n ≤ 1,000,000

---

입출력 예nresult

10	3
12	11

 

 

가장 간단하게 생각하면 1부터 차근차근 나누어 보는 것이다.

차근차근 나누어 1이 아닌경우 1씩 증가시켜서 mod연산으로 비교하는 것이다.

 

class Solution {
    public int solution(int n) {        
        int answer = 1;
        while(true) {
            if (n % answer == 1) {
                return answer;
            }
            answer++;
        }
    }
}

 

그러나 n의 범위가 1000000정도 인데 이 방식은 비효율 적이긴 하다.

O(n)이기 때문이다.

 

다른 방식으로 생각한 것은

n - 1을 나누어 0으로 떨어지게하는 수중 가장 작은 수를 구하면 되지 않을까 생각했다.

따라서 n - 1의 약수중 1을 제외한 최소의 수를 구하면 되지 않을까 생각했다.

시간제약 때문에 모두 구현해보지는 못했다.

나중에 한번 시도를 해보도록 하겠다.