Programmers - 나머지가 1이 되는 수 찾기(Python)

IRISH·2022년 3월 22일

프로그래머스

목록 보기

9/29

문제

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

제한사항

3 ≤ n ≤ 1,000,000

입출력 예

num	return
10	3
12	11

입출력 예 설명

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

✍ 코드 - 초기 풀이


# (1)

from primePy import primes

def solution(n):
    answer = 0 

    primes_to_n = primes.upto(n)
   
    print(primes_to_n)


    for i in primes_to_n:
        if n % i == 1:
            print(i)

			answer = i
            break

    return answer

n = 10
print(solution(n)) # 출력 예 : 3

(1) : 이 문제는 소수를 이용하여 문제를 해결하고자 했다. 주어진 숫자가 n일 때 n이하의 모든 소수를 판별하고 n을 n 이하의 소수로 나눴을 때 나머지가 1이 나올 수 있게 하는 모든 소수 중 가장 작은 소수가 나올 수 있도록 하기 위해서 primePy 라이브러리의 primes를 import 하려고 했었다. 프로그로밍 상에는 문제가 발생하지 않았으나, 해당 문제를 프로그래머스 내에서 코드 실행을 하면
와 같은 메시지가 출력됐다. 따라서 이 방식은 프로그래머스 상에서는 적합하지는 않았다. 그러나 primePy 라이브러리라는 존재를 알게 된 것에 만족한다.

✍ 코드 - 최종 풀이

def solution(n):
    answer = 0 

    # (1)
    sieve = [True] * n

    # (2)
    m = int(n ** 0.5)

    for i in range(2, m + 1):
        if sieve[i] == True: # (3)
            for j in range(i+i, n, i): # i (4)
                sieve[j] = False

    # (5)
    # (6)
    seive_list = [i for i in range(2, n) if sieve[i] == True]

    # (7)
    # (8)
    for value in seive_list:
        if n % value == 1:
            answer = value
            break

    return answer

n = 12
print(solution(n)) # 출력 예 : 3

해당 문제는 '에라토스테스의 체' 방법을 활용해서 문제를 풀었다.
(1) : 에라토스테네스의 체 초기화 : n개 요소에 True 설정(소수로 간주)
(2) : n의 최대 약수가 sqrt(n) 이하이므로 i = sqrt(n)까지 검사
(3) : i가 소수인 경우
(4) : i 이후 i 배수들을 False 판정
(5) : sieve를 통해 얻은 소수 목록을 seive_list에 대입
(6) : 참고로 seive 자체의 리스트 요소들을 True 또는 False로 이루어짐
(7) : seive_list 안에 있는 소수 요소들 중에서 문제가 요구하는 가장 작은 수 찾기
(8) : 가장 작은 수를 찾으면 for문을 종료함

📝 결과

😃 느낀점

'에라토스테스의 체'에 대해서 처음 알게 되었다. 만약 나였다면 2부터 n까지 하나하나 구했을 것 같은데, 시간을 더 절약할 수 있는 방식을 알게 되어 뿌듯하다.
또한, 초기 풀이에서 PrimePy 라이브러리에 대한 것도 알게 되었다. 사실 Visual Studio에서 실행 시간만 놓고보면 PrimePy 라이브러리로 돌리는 것이 '에라토스테스의 체' 보다 훨씬 빠르지만, 프로그래머스에서는 실행이 안되니 이 점은 다소 아쉬웠다.