코테28) 나머지가 1이 되는 수 찾기

📝 문제설명

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

제한사항
3 ≤ n ≤ 1,000,000
입출력 예
n result
10 3
12 11

내 풀이:

def solution(n):
    answer = []
    for i in range(1, n):
        if len(answer) == 1: break
        if n % i == 1 :
            answer.append(i)
    return answer[0]

i) 먼저 찾아야 할 것은 n보다 작은 수에서 n으로 나눈 나머지가 1인 수
-> 1 - (n-1) 를 for loop를 돌렸고 if statement 를 통해 찾으면 answer list에 저장
ii) 가장 작은 수만 찾으면 되니까 len(answer) == 1 이 되면 break를 해서 리턴해버리기
Time complexity: O(n)

처음에는 나머지가 1인 수들을 리스트에 넣어 index 0을 리턴하려 했는데 생각해보니까 가장작은 수만 구하면 되는데 굳이 다 봐야할까하는 생각이 들었다
그래서 리스트길이를 1이 되면 for loop를 끝내고 index 0을 리턴했다. 그리고 지금 다시 생각해보니 answer = 0으로 지정하고 첫번째 if statement를 지운 후 두번째 if statement에서 바로 리턴하면 되겠다는 생각이 들었다

✔ Tips to improve

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

Time complexity: O(n)

너무 간단해져서 머쓱해진 문제...이렇게 하니 실행시간도 짧아졌다