[Programmers | Java | 월간 코드 챌린지 시즌3 문제 풀이] 나머지가 1이 되는 수 찾기 - Solution with Loop & Arithmetic Operator

KDT 실무형 스프링 백엔드 엔지니어 양성과정 6기 | Algorithm CODEKATA

➗ 나머지가 1이 되는 수 찾기

🏷 관련 주제 : 반복문 연산자 나머지 연산자 조건문

문제 설명

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

---

제한사항

• 3 ≤ n ≤ 1,000,000

---

입출력 예

n	result
10	3
12	11

---

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

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

---

✔ Solution with Loop & Arithmetic Operator

class Solution {
    public int solution(int n) {
        int x = n - 1;

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

        return x;
    }
}

채점 결과

---

💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍

📌 오늘 만난 문제의 : 매개변수로 받은 n을 자연수 x로 나눈 나머지가 1이 되게 하는 가장 작은 x를 반환하시오.

---

1은 모든 수의 약수이므로 1은 x가 될 수 없다.
최악의 경우라도 n을 n - 1로 나누면 나머지가 1이므로
문제의 조건을 만족하는 자연수 x는 n - 1로 존재함을 알 수 있다.

1. 반환할 값을 담을 변수 x를 n - 1로 초기화 하자.

(n - 1은 최악의 경우 x가 갖게 될 값)

int x = n - 1;

x는 1이 될 수 없고
x에 이미 n - 1이 할당되어 있으므로
반복문은 2부터 n - 2까지의 범위만 돌리면서 n을 나눈 나머지가 1인 n - 1보다 작은 자연수가 존재하는지 체크할 것이다.

2. int 변수 i의 값이 2부터 n - 2까지 1씩 순차적으로 증가하도록 하면서 반복문을 돌리자.

for (int i = 2; i < n - 1; i++) {
    ...
}

3. 변수 i로 n을 나누었을 때, 나머지가 1이면 x에 i를 할당하고 반복문을 멈추자.

if(n % i == 1) {
    x = i;
    break;
}

4. 반복문이 끝나면 x에 할당된 값을 반환하자.

return x;

💬 무엇을 새롭게 알았는지

문제에서 답이 왜 항상 존재하는지,
최악의 경우 반한될 값은 얼마인지 등을 생각하면서 초기값을 할당하고
반복문의 범위를 정하면서 코드를 작성해 보았다.

---

📚 References(참고 자료)

• [Java 봐] Operators(연산자)