[파이썬 알고리즘 문제풀이 입문] 코드 구현력 기르기 - 뒤집은 소수

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 수를 출력하는 프로그램을 작성하세요.•••

 

 

 

풀이

• 내 풀이

import sys
input = sys.stdin.readline

N = int(input())
nums = list(input().split())

def reverse(x):
    result = ''
    for i in range(0, len(x))[::-1]:
        result += x[i]
    return int(result)

def isPrime(x):
    if x == 1:
        return 0
    for i in range(2, x):
        if x%i == 0:
            return 0
    else:
        return x
        
for i in nums:
    reversed_num = reverse(i)
    if isPrime(reversed_num) != 0:
        print(reversed_num, end=' ')

 

• 답안 : Python

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))

def reverse(x):
    res = 0
    while x>0:
        t = x%10
        res = res*10 +t
        x = x//10
    return res

def isPrime(x):
    if x == 1:
        return False
    for i in range(2, x//2+1):
        if x%i == 0:
            return False
    else:
        return True

for i in nums:
    reversed_num = reverse(i)
    if isPrime(reversed_num):
        print(reversed_num, end=' ')

 

• 답안 : Kotlin (내가 바꿔본 것 / 정확X)

import java.io.*
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    var N = readLine().toInt()
    var nums = readLine().split(" ").map{ it.toInt() }
    var reversed_num = 0

    for(i in nums) {
        reversed_num = reverse(i)
        if (isPrime(reversed_num)) {
            print("${reversed_num} ")
        }
    }
}

fun reverse(x : Int) : Int {
    var num = x
    var res = 0
    while(num > 0) {
        var t = num%10
        res = res*10+t
        num = num/10
    }
    
    return res
}

fun isPrime(x : Int) : Boolean {
    var num = x
    var result = true
    
    if (num == 1) result = false
    
    for(i in 2 until (x/2+1)) {
        if(num%i == 0) {
            result = false
            break
        } else {
            result = true
        }
    }
    
    return result
}

 

- reverse() 함수의 큰 흐름은 비슷한데, 문자로 접근했냐 / 숫자로 접근했냐 차이인 것 같다. (나는 문자, 답안은 숫자)

- isPrime() 함수 같은 경우, 나는 소수이면 해당 x를 반환하고 / 소수가 아니면 0을 반환한다.

   반면, 답안은 소수이면 True를 반환하고 / 소수가 아니면 False를 반환한다. (for~else~ 문을 사용한 것은 동일하다.)

 

 

 

** 빠르게 소수 구하는 알고리즘1

답안에서 for문을 돌릴 때, 2부터 x를 2로 나눈 절반까지 돌린다.

→ why? 1과 x 자기자신을 제외하고, 그 다음 약수를 살펴보면 어떤 수와 x의 절반이 곱해지기 때문!

→ ex) 16 = 1x16 = 2x8

 

 

*** 빠르게 소수 구하는 알고리즘2

x의 제곱근까지만 살펴봐도 된다. (import math / math.sqrt(x))

→ why? 약수의 성질 때문에, 가운데 수를 기준으로 대칭적으로 곱을 통해 x를 만들 수 있다!

ex) 16의 약수 : 1, 2, 4, 8, 16 / 16의 제곱근 = 4

→ 시간복잡도 : O(X^(1/2))

 

   

*** 빠르게 소수 구하는 알고리즘3 : '에라토스테네스의 체'

범위에 대한 소수 판별에 유리한 편이다. (단, 메모리가 많이 필요하다.)

→ 시간복잡도 : O(Nlog(logN))