프로그래머스 - 나머지가 1이 되는 수 찾기

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

 

(입출력 예시)

n	result
10	3
12	11

풀이

def solution(n):
    for x in range (1,n):
        if n % x == 1:
            return x

해설:

1. for문을 통해 n을 나누었을 때 1이 남는 자연수 x를 찾을 때 까지 반복해서 나눗셈을 수행한다. 

2. 만약 1이 남는 자연수 x를 찾았을 경우 그 값을 리턴한다.

 

다른 사람의 풀이

 

- 이 분은 제한사항이었던 3 ≤ n ≤ 1,000,000를 고려해서 풀었다.

def solution(n):

    if not 3 <= n <= 1000000 :
        return False

    answer = 2
    while True :
        if n % answer == 1 :
            break
        else :
            answer += 1

    return answer

 => 제한사항이 아니면 False를 리턴하고, 

answer가 1씩 커지며 n을 나누었을 때 1이 나올때까지 반복한다.

n을 answer로 나눈 나머지가 1이 되는 값을 찾았을 때, answer의 값을 리턴한다.

 

<<정답이 아닐 경우 발생하는 상황 까지 고려하는 코드를 짜자>>.