📝 문제 설명
> 양의 정수n이 주어집니다. 이 숫자를k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
- 0P0처럼 소수 양쪽에 0이 있는 경우
- P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
- 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
- P처럼 소수 양쪽에 아무것도 없는 경우
- 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
- 예를 들어, 101은 P가 될 수 없습니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.
정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.
- 2번째 예시 : 110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다. (출처 : 프로그래머스)
https://programmers.co.kr/learn/courses/30/lessons/92335
🎨 풀이
💡 전체 코드
def sosu(number):
for j in range(2,int(number**0.5)+1):
if number % j == 0:
return 0
return 1
def jinsu(n, q):
rev_base = ''
while n > 0:
n, mod = divmod(n, q)
rev_base += str(mod)
return rev_base[::-1]
def solution(n, k):
answer = 0
n = jinsu(n,k)
n = str(n).split("0")
for i in range(len(n)):
if n[i] == "1" or n[i] == '':
continue
number = int(n[i])
if sosu(number) == 1:
answer += 1
return answer
> 문제에서 나온 그대로 주어진 정수 n을 k진수 형태로 변환하고, 그 후에 조건에 맞는 소수가 몇 개인지 체크하면 된다!
# solution 함수 (main부분)
n = jinsu(n,k)
1. n을 jinsu 함수를 통해 k진수 형태로 변환시킨 후 넣어준다.
# jinsu 함수
def jinsu(n, q):
rev_base = ''
while n > 0:
n, mod = divmod(n, q)
rev_base += str(mod)
return rev_base[::-1]
(while문 - 2,3,4번)
2. divmod를 이용해 n에는 몫(n // q), mod에는 나머지(n % q)를 넣어준다.
3. rev_base에 mod 값을 넣어준다.
4. 이 작업을 n이 0보다 크다면 계속 반복한다.
5. while문 작업이 끝나면, rev_base에 들어가있는 값을 처음부터 끝까지 역순으로! 바꿔준다.
이 과정을 그림으로 나타내보자면,
이와 같다. 10을 2진수로 바꾸는 작업을 예시로 들어보았다. 계속 몫과 나머지에 새로운 값이 들어오고, 그 나머지 값들은 rev_base에 거꾸로 저장이 되어있다. 그래서 마지막에 while문을 끝낸 후 거꾸로 뒤집어주는 작업을 하는 것이다.
# solution 함수 (main부분)
n = str(n).split("0")
for i in range(len(n)):
if n[i] == "1" or n[i] == '':
continue
number = int(n[i])
6. k진수로 변환이 잘 되었으니, 이제 0을 기준으로 문자를 나눠준다.
- 조건에서 0을 기준으로 왼쪽, 오른쪽, 양옆 뭐 이런식으로 다 구분을 해줘야한다고 해서 0을 기준으로 split을 한 것이다.
어짜피, 소수는 0이 없어야한다고 했으니까 0을 기준으로 나눠주는게 맞다고 생각한다.
7. for문을 통해, 만약 n[i]가 1이거나 공백이라면 패스시키고, 아니라면 소수 함수를 돌려준다.
# sosu 함수
def sosu(number):
for j in range(2,int(number**0.5)+1):
if number % j == 0:
return 0
return 1
8. 2부터 num의 제곱근 + 1 까지 나눠보고, 나눠진다면 바로 return 0을 해버린다.
- 범위가 이런 이유는, 이거보다 이상으로 나눈거나 이거나 똑같기 때문이다.
9. 만약 끝까지 안나눠졌다면 return 1을 한다.
# solution 함수 (main부분)
if sosu(number) == 1:
answer += 1
return answer
10. 만약 sosu 함수에서 1을 리턴받았다면, answer += 1을 해준다. (answer에 1을 더해줌)
11. 그대로 answer를 리턴해주면 끝이 난다!
끝~
⭐ 느낀점
> 인터넷 보다보니까, 이런 느낌으로 정리한 분이 있던데 약간 거기서 영감을 받아보긴했다. 근데,, 잘 정리된건지 모르겠다. 이해가 잘 되려나?! 내 꺼를 좀 수시로 보면서 이해가 되는 지 확인을 해봐야할 것 같다. 하하 파이팅 ^ㅁ^
'알고리즘 공부 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 / Level 1] 성격 유형 검사하기 (파이썬) (0) | 2022.09.15 |
---|---|
[프로그래머스 / Level 2] 이진 변환 반복하기 (파이썬) (0) | 2022.09.14 |
[프로그래머스 / Level 1] 정수 제곱근 판별 (파이썬) (0) | 2022.05.14 |
[프로그래머스 / Level 1] 최소직사각형 (파이썬) (0) | 2022.05.13 |
[프로그래머스 / Level 1] 나머지가 1이 되는 수 찾기 (파이썬) (0) | 2022.05.12 |