[프로그래머스] 코딩테스트 연습 - 나머지가 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 해야 합니다.

풀이 과정

1. 문제의 포인트는 나머지는 1과 가장 작은 수이다.

2. 이렇게 생각하였을 때 주어지는 숫자는 1이 남아야 하기 때문에 1을 빼서 나누었을 때 나누어 떨어진다고 생각이 가능하다.

3. 이를 이용하기 위해서는 나머지를 구하는 %를 사용할 수 있다.

4. 주어진 숫자에서 1을 빼준 숫자를 %로 나누어 주도록 한다. 이때 0이 나오면 나머지가 1이 나오게 하는 숫자로 판단이 가능하다.

5. 한 가지 숫자를 나누었을 때 1을 빼고 수행하면 나누어 떨어지는 숫자가 여러 개가 있을 수 있는데 이 중 가장 작은 수를 구하기 위해서 for문을 이용해서 가장 작은 숫자부터 1씩 증가될 수 있게 구성한다.

6. 작은 수부터 점점 증가하면서 수행했을 때 첫 번째로 성립하는 숫자를 answer변수에 저장하고 for문을 종료 이것을 리턴해 주도록 한다.

 

코드

def solution(n):
    check = n - 1
    answer = 0
    for i in range(2, check + 1):
        if check % i == 0:
            answer = i
            break

    return answer