[Java] 나머지가 1이 되게 하는 최소값 찾기.

Problem 💻

https://school.programmers.co.kr/learn/courses/30/lessons/87389

프로그래머스

 

문제 설명

자연수 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 해야 합니다.

 

---

Approach 2 ⭕ - 논리적 접근법

문제 요약 :

자연수 n을 x로 나눴을 때 나머지가 1이 되는 가장 작은 자연수 x를 찾는 문제이다.

 

문제 해결을 위한 핵심 개념 :

1. 나머지 연산의 정의 :

수 n을 x로 나누었을 때, n % x =1을 만족하는 가장 작은 x를 찾는 것이다.

 

2. 조건 분석 :

n%n=1이 성립하려면 n에서 1을 뺀 값이 x로 나누어떨어져야 한다.

즉,n-1x

따라서 x는 n-1의 약수중에서 1보다 큰 가장 작은 자연수이다.

예를 들어 10을 3으로 나누면 몫이 3이고 나머지가 1이다.

10 = 3*3+1

나머지는 숫자를 나눴을 때 딱 떨어지지 않고 남는 부분이다.그래서 n-1 = y * xx가 1이면 나머지는 0이므로 x는 2 이상이다. 

 

3. 범위의 제한 :

x는 자연수이므로 x>= 1이어야 한다.

x=1일때 n%n=0이므로, 조건을 만족하려면 x >=2부터 시작한다.  

 

---

문제 해결 방법

1. 수학적 접근 :

n-1을 구한다.

n-1의 약수를 구하면서 x >=2인 가장 작은 값을 찾는다. 

 

2. 효율적 반복 :

x를 2부터 시작하여 n%n=1이 되는 x를 찾는다.

x가 n-1의 약수임을 확인하는 방식으로 구현 가능하다. 

x를 2부터 차례로 1씩 늘려가니깐 나머지가 1이 되는 순간의 x가 최소값이다.

---

논리 단계별 설명

1. 입력 확인 :

자연수 n이 주어진다.

 

2. 반복문으로 조건 확인 :

x를 2부터 n-1까지 반복한다.

n%n=1인 경우 x를 반환한다.

x를 2부터 하나씩 더해 보면서 n%x=1이 되는지 확인한다.

 

3.출력 :

항상 답이 존재하므로, 반복문 안에서 조건이 만족되는 즉시 x를 반환한다. 

숫자 n-1은 항상 존재하고 , x는 n-1의 약수 중 하나일 수 밖에 없다.

---

Solution 💡

public class Solution {
   public int solution(int n) {
      // x는 1부터 시작하여 n을 x로 나눈 나머지가 1인 경우를 찾는다.
      for (int x = 1; x < n; x++) {
          if (n % x == 1) {
               return x; //조건을 만족하는 x를 반환한다. 
          }
      }
      return -1 // 답이 항상 존재하므로 이 코드는 실행되지 않는다. 
   }
}

---

Reference 📄