[Programmers] 나머지가 1이 되는 수 찾기

문제 설명

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

---

제한사항

• 3 ≤ n ≤ 1,000,000

---

입출력 예

nresult

10	3
12	11

---

입출력 예 설명

입출력 예 #1

• 10을 3으로 나눈 나머지가 1이고, 3보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 3을 return 해야 합니다.

입출력 예 #2

• 12를 11로 나눈 나머지가 1이고, 11보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 11을 return 해야 합니다.

---

풀이코드

// 짝수일때는 무조건 답은 홀수로 나오고
// 홀수일때는 무조건 답이 짝수로 나오니까 불필요한 반복문을 줄이자
class Solution {
    public int solution(int n) {
        int answer = 2; // 3부터 시작이니까 나누기 시작하는수는 2부터시작한다
        
        // 짝수일땐 홀수로 나눠주기
        if(n%2 == 0) {
            answer = 3;
        } else {
            return 2; // 홀수면 최소수는 무조건 2다
        }
        
        // 반복문 돌리고 나머지가 1로 떨어지는 최소 수 찾기
        while(answer < n) {
            if(n%answer == 1) {
                return answer; // 찾았으면 걔가 최소수니까 더이상 반복 하지말자
            }
            answer += 2;
        }
        return answer;
    }
}

---

풀이방법

제목 그대로 나머지값이 1이 되는 최소 수를 찾는문제이다. 반복문을 한번 돌려서 증가되는만큼 나눠보고 나머지가 1이 나오면 최소수 이므로 return 해주면된다. 반복문을 최대한 줄이고싶어서 몇가지 조건을 줬다

1. 문제에서 주어지는 n은 3부터 시작이므로 0,1,2가 들어오는경우가 없다 그말은 즉, 2부터 나눠보기 시작하면 된다는거다.
2. 2로 나눠줄 값을 선언부터 해준다.
3. n이 만약 짝수가 들어온다면 ex) 2, 4, 6, 8, 10, 12 면 나머지가 1이 되는 최소수는 무조건 홀수일것이다. 왜냐면 짝수는 무조건 나눠지고 나머지가 남지않으니까... 
4. 홀수는 최소수가 무조건 2다 홀수로 왔으면 어떻게 하든 나머지값이 1이 되려면 짝수로 나눠줘야하는데 2로는 모든 짝수를 나눌수있다. 그니까 바로 return 해주면 된다.
5. 그렇게 나눠서 제일먼저 1이 남는 수를 return 한다.