[python]나머지가 1이 되는 수 찾기

월간 코드 챌린지 시즌3>나머지가 1이 되는 수 찾기

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

[제한사항]

• 3 ≤ n ≤ 1,000,000
  
  

[입출력 예]

[입출력 예 설명]

입출력 예 #1

10을 3으로 나눈 나머지가 1이고, 3보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 3을 return 해야 합니다.

입출력 예 #2

12를 11로 나눈 나머지가 1이고, 11보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 11을 return 해야 합니다.

나의 풀이

생각해보기!

def solution(n):
    for i in range(1,n):
        if n%i == 1:
            answer =i
            break
    return answer

• % : 나눴을 때 나오는 나머지 반환하는 기호
  

문제가 쉬웠다! 다양한 풀이법이 있는데 모두 알아두자~😇

다른 사람의 풀이 #1

def solution(n):
    answer = 0

    for divisior in range(2, (n-1//2) +1) : #2부터~반값까지 
        if (n-1) % divisior == 0: #약수가 있다면
            answer = divisior 
            break #탈출
        else: 
            answer = n-1 #약수가 없다면 본인
    return answer

참고하세요!

• 약수가 있는 경우와 없는 경우를 나누었다.
• 제한사항의 n의 범위가 3부터 시작이므로 범위를 2부터 시작했다.
• 주어진 n의 절반이 넘는 숫자로 나눴을 때 나머지가 1인 경우는
  n-1인 경우 뿐이다.

다른 사람의 풀이 #2

def solution(n):
    answer = min([x for x in range(1, n+1) if n % x == 1])
    return answer

참고하세요!

• n%x 가 1이 되는 경우를 리스트로 받고 그 중 최솟값을 출력했다.

다른 사람의 풀이 #3

def solution(n):

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

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

    return answer

참고하세요!

• 제한 사항인 n의 범위를 고려했다.
• while 문으로 참이 될 때까지 반복문을 실행하여 answer에 +1씩 해주었다.
  • answer를 x로 지정하여 2부터 +1씩 늘려나갔다.