728x90
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(참고 자료)
728x90
