#AIL_23.11.17 // Programmers_나머지가 1이 되는 수 찾기

## AIL_나머지가 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.JavaScript

1. 문제의 접근 방식

주어진 문제는 어떤 자연수 n을 x로 나눴을 때, 나머지가 1이 되는 가장 작은  자연수 x를 찾는 문제입니다. (제한된 범위)

---

2. 문제풀이

function solution(n) {
    for (let i = 2; i < n; i++) {
        if (n % i === 1) {
            return i;
        }
    }
    return n - 1; // 조건을 만족하는 수가 없을 때, n-1을 반환
}

/*
테스트 1
입력값 〉	10
기댓값 〉	3
실행 결과 〉	테스트를 통과하였습니다.
테스트 2
입력값 〉	12
기댓값 〉	11
실행 결과 〉	테스트를 통과하였습니다.
*/

 

위 코드는 `for` 반복문을 사용하여 `i`를 2부터 n-1까지 증가시키면서 주어진 수 n을 해당 수 i로 나누었을 때 나머지가 1이 되는 경우를 찾습니다.

 

1. `for` 반복문에서 `i`가 2부터 시작하여 n-1까지 증가합니다. 이때, 1은 나누는 수로 사용하지 않는 이유가 모든 수를 1로 나누면 나머지가 0이 되기 때문입니다. 

 

2. 각 `i`에 대해 `n%1`을 계산하여 나머지가 1인지 확인합니다. 나머지가 1이면 해당 수 i를 반환합니다. 

 

3. 만약 조건을 만족하는 수가 없다면, `return n-1;`을 통해 n-1을 반환합니다. 이 경우 주어진 수가 아주 큰 소수인 경우에 해당합니다 .소수인 경우에는 자연수 범위 내에서 1을 제외한 어떤 수든 소수 자신을 제외하고 나누었을 때, 나머지가 1이 되는 수가 존재하지 않습니다. 그렇기 대문에 소수인 겨우 n-1을 반환하여 처리합니다. 

---

3. 다른사람의 문제풀이 및 접근방식 분석(1)

function solution(n, x = 1) {    
    while (x++) {
        if (n % x === 1) {
            return x;
        }
    }    
}
/*
테스트 1
입력값 〉	10
기댓값 〉	3
실행 결과 〉	테스트를 통과하였습니다.
테스트 2
입력값 〉	12
기댓값 〉	11
실행 결과 〉	테스트를 통과하였습니다.
*/

 

1. `n`은 주어진 자연수이며, 나머지가 1이 되는 `x`를 찾아야 합니다. 

 

2. `x`는 기본적으로 1로 설정됩니다. 이 값은 함수에 전달되지 않으면 1로 자동으로 초기화 됩니다. 

 

3. `while` 루프는 `x`를 1부터 시작하여 1씩 증가시키고 무한 반복합니다. 

 

4. 각각의 `x` 값에 대대 `n % x`를 계산하여 나머지가 1인지 확인합니다. 

 

5. 만약 나머지가 1이면 해당 `x` 값을 반환하고 함수 실행을 종료합니다. 

 

이 함수의 특징은 무한 루프에 빠질 수 있는데, `while` 루프 내에서 `x++`로  `x`의 값을 1씩 증가시키기 때문입니다. 하지만 주어진 `n` 값은 최대 1,000,000까지이므로, `x` 값이 `n`을 넘지 않도록 설계되어 있습니다.  

---

4. 다른사람의 문제풀이 및 접근방식 분석(2)

function solution(n, x = 0) {
     return n % x === 1 ? x : solution(n, x + 1);
 }
 /*
테스트 1
입력값 〉	10
기댓값 〉	3
실행 결과 〉	테스트를 통과하였습니다.
테스트 2
입력값 〉	12
기댓값 〉	11
실행 결과 〉	테스트를 통과하였습니다.
*/

 

이 함수는 재귀적인 방법을 사용하여 문제를 해결하려고 합니다. 주어진 자연수 `n`과 `x`의 값을 비교하여 `n % x ===1` 조건을 만족하는지 확인합니다. 만약 조건을 만족하면, 해당 `x` 값을 반환하고 함수를 종료합니다 .

 

그렇지 않으면 `x` 를 1씩 증가시킨 새로운 `x + 1` 값으로 다시 `solution` 함수를 호출합니다. 이렇게 계속해서 `x` 값을 증가시키며 `n % x  === 1` 조건을 만족하는 가장 작은 ` x` 값을 찾는 방식입니다. 

---

# 재귀적인 방법(Recursion)이란? 

재귀적인 방법(Recursion)은 함수가 자기 자신을 호출하여 해결하려는 문제를 작은 부분으로 쪼개어 해결하는 방법입니다. 이것은 함수가 작은 문제를 해결할 수 있는 기본 케이스(Base Case)에 도달할 때까지 반복됩니다. 

 

# 3항 연산자란?? 

3항 연산자는 JavaScript와 같은 많은 프로그래밍 언어에서 사용되는 조건식입니다.

조건 ? 값1 : 값2

 

이 연산자는 조건을 검사하고, 조건이 참이면 `값1`을 반환하고, 조건이 거짓이면 `값2`를 반환합니다. 따라서 조건문을 간단하게 표현할 수 있게 해줍니다. 

 

바로 위에 코드에서 사용된 3항 연산자는 다음과 같습니다. 

return n % x === 1 ? x : solution(n, x + 1);