[프로그래머스] 나머지가 1이 되는 수 찾기_Python level1

🔒 문제

https://programmers.co.kr/learn/courses/30/lessons/87389

코딩테스트 연습 - 나머지가 1이 되는 수 찾기

 

문제 설명

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

---

제한사항

• 3 ≤ n ≤ 1,000,000

---

입출력 예

n	result
10	3
12	11

---

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

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

---

🔓 풀이

🔑 요구사항 파악

1. 요구사항 : 자연수 N을 X로 나눈 나머지가 1이 되는 가장 작은 자연수 찾기

2. Type

 - Input | n: int (3<=n<=1,000,000)

 - Output | answer: int

---

🔑 문제 해결 방법 고민하기

1 자연수 N을 X로 나눈 나머지가 1이 되는 가장 작은 자연수 찾기
 - 답이 될 수 있는 가장 작은 수인 2부터 1씩 더한 수 x로 차례대로 나누어 나머지가 1인 x 찾기

 

<고민의 흔적>

---

🔑 문제 해결 / 코드

def solution(n):
    answer = 2

    while n % answer != 1:
        answer += 1

    return answer


print(solution(10))
print(solution(12))

---

💉 피드백

1. 접근 방법

정답이 될 수 있는 가장 작은 자연수인 2부터 시작해서 정답이 나올 때까지 1씩 더한 수 나누기를 반복하는 while 반복문을 사용해서 문제 해결. n의 범위가 3 <= n <= 1,000,000 이어서 차례대로 계산해도 성능에 문제가 없을 거라 생각했다(시간 복잡도)

 

2. 다른 사람 풀이

답안을 제출하고 다른 사람의 풀이를 보다 보니 코드 몇 줄 추가로 효율(성능)을 증가시킬 수 있을 거 같아서 시도해보았다.

n의 범위에 제한이 없을 경우 좀 더 효율적인 코드가 좋은 답안 같아서 시도.

 

 - 접근 방법

기본 전제는 전과 동일하지만 사실 x가 n의 1/2을 넘어가면 아무리 나누어도 n-1이 되기 전까지는 나머지가 1이 되지 않는다.

ex) 10의 1/2인 5보다 큰 수로 나누게 되면 ( 10 % 6 = 4, 10 % 7 = 3, 10 % 8 = 2, 10 % 9 = 1 ) n - 1인 9로 나눌 때만 나머지가 1이 된다. 

 

따라서 while 반복문에 x 가 n의 1/2 보다 크면 정답을 바로 n-1로 해주는 조건문을 추가하면 끝!

 

# 업그레이드
def solution(n):
    answer = 2

    while n % answer != 1:
        if answer > n/2:
            answer = n - 1
        else:
            answer += 1

    return answer


print(solution(10))
print(solution(12))

 

 

---