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

 

문제

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

 

문제 풀이 접근법 1

처음에는 다음과 같은 알고리즘으로 접근했었다. 

 

1) n 입력 받음

2) for문에서 i를 1씩 증가 → n을 i로 나누었을 때, 나머지가 1인지 확인

3) 만약 나머지가 1이면 해당 i값을 return

*i를 1부터 1씩 증가하므로 처음으로 나머지가 1이 나오는 수가 가장 작은 x일 것

 

 

하지만 결과 값이 예상대로 나오지 않았다. 원래라면 3*3 = 9이므로 n이 10일 때, 나머지가 1이되게 하는 가장 작은 자연수 x는 3이지만 위의 알고리즘에서는 3*1=3이므로 10을 3으로 나눈 나머지는 7이 된다.

 

그래서 다시 고민해다가 생각난 방법이 소수를 사용하는 것이었다. 

 

문제 풀이 접근법2

 

10 - 1 = 9

12 - 1 = 11

7 - 1 = 6

다음과 같이 몇 가지 예제를 적어 보았을 때, n값을 1로 나누었을 때 나오는 몫을 소인수 분해 하면 원하는 대로 가장작은 x값을 찾을 수 있음을 알 수 있었다. 따라서 

 

1) n을 입력 받음 

2) n-1값이 소수인지 확인 

3) 만약 n-1값이 소수라면 그대로 값을 return 

4) n-1값이 소수가 아니라면, n-1의 약수를 구하여 리스트에 저장한 뒤, 가장 작은 약수를 return 

 

def solution(n):
    answer = 0
    N = n-1
    divisor = []
    
    for i in range(2, N):
        if N % i == 0:
            divisor.append(i)
            answer = divisor[0]
            break
            
        else:
            answer = N
    
    return answer

 

처음에는 약수가 잘 생각이 안나서 소인수분해로 접근했었다. 

사실 쉬울 줄 알았는데 은근 고민을 하는 문제였다. 

더 깔끔하게 풀 수 있을 것 같다

나중에 다시 풀어봐야지