(인프런) 파이썬 알고리즘 문제1-8 "뒤집은 소수"

뒤집은 소수

 

[시간복잡도]

O(n)

: for문과 while문을 별도로 한개씩 돌기 때문에 시간복잡도는 O(n)에 해당한다.

[공간복잡도]

O(n)

 

고정공간 : res, n, k (변수)

가변공간 : x, t, tmp

 

Problem

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

예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력 한다.

단 910를 뒤집으면 19로 숫자화 해야 한다.

첫 자리부터의 연속된 0은 무시한다.

뒤집는 함수인 def reverse(x) 와 소수인지를 확인하는 함수 def isPrime(x)를 반드시 작성하 여 프로그래밍 한다.

 

▣ 입력설명

 

첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다. 각 자연수의 크기는 100,000를 넘지 않는다.

 

▣ 출력설명

 

첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.

 

▣ 입력예제

 

5

32 55 62 3700 250

 

▣ 출력예제

 

23 73

 

💯 Solution ①

: 어려워서 튜터님의 코드 참고

 

처음에 접근할 때는

 

(수정 전)

import sys
sys.stdin=open('input.txt','rt')
 
# 다음줄 자연수의 갯수 n
n=int(input())
 
# 두번째 줄 n개의 자연수
k=list(map(int,input().split()))
# k를 뒤집어 놓은 배열 : rev_list
rev_list=[]
# 0을 제거한 배열 : final_list
final_list=[]
 
 
# 숫자들을 뒤집는 함수 : reverse(x)
# x : List
def reverse(x):
    for i in range(len(x)):
        num_list = list(str(x[i]))
        # 리스트 반대로 하고 다시 붙이기
        num_list.reverse()
        rev_list.append(''.join(num_list))
    for j in range(len(rev_list)):
        # 문자열 앞쪽에 0들을 제거한다.
        test=rev_list[j].lstrip("0")
        final_list.append(test)
    return final_list
 
# 소수인지 확인하는 함수 : isPrime(x)
# x : List
def isPrime(x):
    for m in range(len(x)):
        for o in range(2,int(x[m])//2+1):
            if x[m]==1:
                return False
            if x[m]%o==0:
                return False
        else:
            return True, x[m]
 
if isPrime(reverse(k)) == True:
    print(x[m])
 
 

해당 코드처럼 로직을 짜봤는데, for문이 너무 많고 의도한 결과가 제대로 나오지 않아서 튜터님의 코드를 참고하여 다시 작성하였다.

 

(수정 후)

import sys
sys.stdin=open('input.txt','rt')
 
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
 
n=int(input())
k=list(map(int,input().split()))
for x in k:
    tmp=reverse(x)
    if isPrime(tmp):
        print(tmp, end=" ")
 

 

 

💯 Solution ②

: Tutor advice

 

import sys
sys.stdin=open('input.txt','rt')
def reverse(x):
    res=0
    # x가 0이 될때까지 반복
    while x>0:
        # 10으로 나눈 나머지 : t
        t=x%10
        res=res*10+t
        # 10으로 나눈 몫 : x
        x=x//10
    # x를 뒤집은 res를 반환
    return res
    
def isPrime(x):
    # x로 1이 넘어오게 되면 제외시켜야함
    if x==1:
        return false
    # 굳이 x를 다 돌 필요가 없음. 어차피 약수를 찾는 것이기 때문에 x의 절반만 수행 : x//2
    for i in range(2,x//2+1):
        # 약수가 있는 경우
        if x%i==0:
            return false
    # return 당하지 않고 정상적으로 for문이 종료되었다면 else구문 시작
    else:
        return True
 
n=int(input())
a=list(map(int, input().split()))
for x in a:
    # x를 뒤집은 리스트 : tmp
    tmp=reverse(x)
    if isPrime(tmp):
        print(tmp, end=" ")
 

 

- reverse() 함수와 isPrime()함수를 만들어서 코드를 작성

- reverse() 함수는 주어진 값을 거꾸로 뒤집는 기능을 구현해야한다.

: res의 초기값으로 0을 설정 / t : x를 10으로 나눈 나머지 / res=res*10+t : 해당 값을 뒤집는 연산 / x=x//10 : x를 10으로 나눈 몫으로 설정

=> 해당 코드를 반복하면, x가 0이되는 시점이 오는데 그때의 res값이 x를 뒤집는 값이 된다.

 

---

(Tip) 해당 숫자를 뒤집을 때 사용하는 코드 : reverse(x)

def reverse(x):
    res=0
    # x가 0이 될때까지 반복
    while x>0:
        # 10으로 나눈 나머지 : t
        t=x%10
        res=res*10+t
        # 10으로 나눈 몫 : x
        x=x//10
    # x를 뒤집은 res를 반환
    return res

---

 

- isPrime() 함수는 주어진 값이 소수인지 판단하는 함수이다.

: x==1일때, 소수 x => 제외시켜줌 (return false)

 

: 원래는 for문을 x 까지 다 돌아야하지만, 약수를 찾기만하면 끝나기 때문에 (1개라도) 굳이 다 돌지않고 x//2번까지만 돌아도 충분함.  

=> for i in range(2, x//2+1) 이렇게 반복했을 때, x를 나눌 수 있는 i가 있다면 소수가 아님 (return false)

 

: for문을 다 돌아서 정상적으로 빠져나온다면 else구문을 통해서 return true를 하는 구조의 함수코드

 

📚 참고