관리 메뉴

솜씨좋은장씨

[BaekJoon] 1747번 : 소수&팰린드롬 (Python) 본문

Programming/코딩 1일 1문제

[BaekJoon] 1747번 : 소수&팰린드롬 (Python)

솜씨좋은장씨 2021. 9. 28. 00:24
728x90
반응형

코딩 1일 1문제! 오늘의 문제느 백준의 소수&팰린드롬입니다.

 

1747번: 소수&팰린드롬

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고,

www.acmicpc.net

👨🏻‍💻 문제 풀이

입력받은 수 보다 크거나 같으면서 소수의 조건을 만족하고 팰린드롬의 조건을 만족하는 

가장 작은 수를 구하는 문제입니다.

먼저 소수 인지 아닌지를 보는 부분은 에라토스테네스의 체 방법을 활용하였고

팰린드롬은 [::-1] 방법을 활용해 확인하였습니다.

def get_primary_num_eratos(N):
    nums = [True] * (N)
    
    for i in range(2, len(nums) // 2 + 1):
        if nums[i] == True:
            for j in range(i+i, N, i):
                nums[j] = False
    return [i for i in range(2, N) if nums[i] == True]


def is_palindrome(num):
    result = False
    if str(num) == str(num)[::-1]:
        result = True
        
    return result

먼저 에라토스테네스의 체 방법을 활용해 소수를 구하는 get_primary_num_eratos 함수와

[::-1] 방법을 활용해 팰린드롬인지 아닌지 확인하는 is_palindrome 함수를 만들어줍니다.

number = int(input())
    
prime_numbers = get_primary_num_eratos(1000001)

그 다음 기준이 될 수를 입력 받는 부분을 작성하고

입력 받는 수의 범위가 1부터 1000000 이므로 1부터 1000000 사이의 소수를

get_primary_num_eratos를 활용해 구해둡니다.

answer = 0
    
for prime_number in prime_numbers:
    if prime_number >= num and is_palindrome(prime_number):
        answer = prime_number
        break
if answer == 0:
    answer = 1003001

다음으로는 정답 숫자가 될 변수인 answer를 0으로 만들어준 다음

아까 만들어 둔 소수에서 숫자를 하나씩 꺼내오면서 내가 입력했던 수보다 크면서 팰린드롬인 수의 경우

정답값에 넣어주고 반복문을 종료합니다.

만약 반복문이 끝날때 까지 조건에 걸리지 않는 다면 1000000 뒤의 가장 작은 소수이면서 팰린드롬인 수인

1003001값을 정답으로 넣어줍니다.

 

전체 코드는 아래를 참고해주세요.

👨🏻‍💻 코드 ( Solution )

def get_primary_num_eratos(N):
    nums = [True] * (N)
    
    for i in range(2, len(nums) // 2 + 1):
        if nums[i] == True:
            for j in range(i+i, N, i):
                nums[j] = False
    return [i for i in range(2, N) if nums[i] == True]


def is_palindrome(num):
    result = False
    if str(num) == str(num)[::-1]:
        result = True
        
    return result


def primary_num_and_palindrome(num, prime_numbers):
    answer = 0
    is_prime_palindrome = False
    
    for prime_number in prime_numbers:
        if prime_number >= num and is_palindrome(prime_number):
            answer = prime_number
            break
    if answer == 0:
        answer = 1003001
        
    return answer

if __name__ == "__main__":
    number = int(input())
    
    prime_numbers = get_primary_num_eratos(1000001)
    
    print(primary_num_and_palindrome(number, prime_numbers))
 

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07

1일 1문제 since 2020.02.07. Contribute to SOMJANG/CODINGTEST_PRACTICE development by creating an account on GitHub.

github.com

Comments