ํฐ์คํ ๋ฆฌ ๋ทฐ
[ํ๋ก๊ทธ๋๋จธ์ค] Lv2 k์ง์์์ ์์ ๊ฐ์ ๊ตฌํ๊ธฐ
roopreDev 2022. 12. 24. 13:36๐ ๋ฌธ์ ๋งํฌ
https://school.programmers.co.kr/learn/courses/30/lessons/92335
๐ ํ์ด
์ด ๋ฌธ์ ๋ ๊ฐ๋ณ์ ์ผ๋ก ๊ตฌํํด์ผํ ๊ฒ๋ค์ด ๋ง์๋ค.
1. ์ฃผ์ด์ง ์ n์ k์ง์๋ก ๋ฐ๊พธ๊ธฐ
2. ์์ ํ๋ณํ๊ธฐ
3. ์กฐ๊ฑด์ ๋ง๋ ๊ฐ์ ์ฐพ๊ธฐ
์ฃผ์ด์ง ์ n์ k์ง์๋ก ๋ฐ๊พธ๊ธฐ
def getDigit(n, k):
digit = 0
num = 1
while n >= num:
num *= k
digit+=1
return digit
์์ ํ๋ณํ๊ธฐ
์ฒ์์๋ ์๋์ ๊ฐ์ด ์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ฅผ ์ด์ฉํด ๊ตฌํํ๋ค.
def setIsPrime():
MAX_NUM = 60000001
isPrime = [True for i in range(MAX_NUM)]
isPrime[0] = False
isPrime[1] = False
isPrime[2] = True
for i in range(2,MAX_NUM):
if isPrime[i] == True:
for j in range(2,(MAX_NUM//(i))):
isPrime[i*j] = False
return isPrime
ํ์ง๋ง ๋ฌธ์ ์กฐ๊ฑด์ ์ดํด๋ณด๋ฉด 1 <= n <= 1000000, 3 <= k <= 10 ์ด๊ธฐ ๋๋ฌธ์ 100๋ง์ด๋ผ๋ ์๋ฅผ 3์ง์๋ก ๋ฐ๊ฟจ์ ๋ ์ซ์ ๊ธธ์ด๊ฐ ๋๋ฌด ๊ธธ์ด์ง๋ค. ๋ฐ๋ผ์ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ฅผ ์ด์ฉํด ์์ ํ๋ณ ๋ฐฐ์ด์ ๋ง๋ค์ด ๋๋ ๊ฒ ๋ณด๋ค๋ ์๋์ ๊ฐ์ด ๊ณจ๋๋ฐํ์ ์ถ์ธก์ ์ด์ฉํด ๊ทธ๋ ๊ทธ๋๋ง๋ค ์์ ์ฌ๋ถ๋ฅผ ํ๋ณํ๋๊ฒ ๋ ํจ์จ์ ์ด๋ค.
def prime(n):
if n <= 1: return False
i = 2
while i*i <= n:
if n%i == 0: return False
i += 1
return True
์กฐ๊ฑด์ ๋ง๋ ๊ฐ์ ์ฐพ๊ธฐ
์กฐ๊ฑด์ ๋จผ์ ์ดํด๋ณด๋ฉด ์๋์ ๊ฐ๋ค.
์ด ๋ถ๋ถ์ stack์ ์ด์ฉํ๋ค. 0์ด ๋ค์ด์์ ๋ stack์ด ๋น์ด์์ง ์์ผ๋ฉด ์๋ฅผ ๊ณ์ฐํ์ฌ ์์ ์ฌ๋ถ๋ฅผ ํ๋ณํ๊ณ stack์ ๋น์์ค๋ค. 0์ด ์๋๋ฉด stack์ ์ถ๊ฐํด์ค๋ค. ์ฌ๊ธฐ์ ์ฃผ์ํ ์ ์ด ๋ฐ๋ณต๋ฌธ์ด ๋๋๊ณ stack์ด ๋น์ด์์ง์์ผ๋ฉด ํ๋ฒ ๋ ์กฐ๊ฑด์ ๋ง๋์ง ํ์ธํด์ค์ผํ๋ค.
stack = []
cnt = 0
for i in range(len(toDigit)):
if toDigit[i] != '0':
stack.append(toDigit[i])
else:
if len(st) != 0:
if prime(int(''.join(stack))):
cnt+=1
stack = []
if len(stack) != 0:
if prime(int("".join(stack))):
cnt+=1
์ ์ถ ์ฝ๋
def prime(n):
if n <= 1: return False
i = 2
while i*i <= n:
if n%i == 0: return False
i += 1
return True
# ์ง์๋ก ๋ณํํด์ฃผ๋ ํจ์
def getDigit(n, k):
digit = 0
num = 1
while n >= num:
num *= k
digit+=1
return digit # ์๋ฆฌ์ 4๊ฐ
def solution(n, k):
toDigit = ""
digit = getDigit(n,k)
while digit > 0:
digitNum = k**(digit-1)
if k**(digit-1) <= n:
toDigit += str((n//digitNum))
n -= ((n//digitNum)*digitNum)
else:
toDigit += '0'
digit -= 1
# ------- ์ง์ ๋ณํ ๋
"""
0P0์์ ์์ชฝ์ 0์ด ์๋ ๊ฒฝ์ฐ
P0 ์์ ์ค๋ฅธ์ชฝ์๋ง 0์ด ์๊ณ ์ผ์ชฝ์๋ ์๋ฌด๊ฒ๋ ์๋ ๊ฒฝ์ฐ
0P ์์ ์ผ์ชฝ์๋ง 0์ด ์๊ณ ์ค๋ฅธ์ชฝ์๋ ์๋ฌด๊ฒ๋ ์๋ ๊ฒฝ์ฐ
"""
stack = []
cnt = 0
for i in range(len(toDigit)):
if toDigit[i] != '0':
stack.append(toDigit[i])
else:
if len(st) != 0:
if prime(int(''.join(stack))):
cnt+=1
stack = []
if len(stack) != 0:
if prime(int("".join(stack))):
cnt+=1
return cnt
'Algorithm > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] Lv3 ๊ธฐ๋ฅ๊ณผ ๋ณด ์ค์น (0) | 2023.01.14 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค] LV3. ๋ค๋จ๊ณ ์นซ์ ํ๋งค (1) | 2023.01.04 |
[ํ๋ก๊ทธ๋๋จธ์ค] Lv2 ํ ์ธ ํ์ฌ (0) | 2022.12.28 |
- Total
- Today
- Yesterday
- ์ฝ๋ฉํ ์คํธ
- ํ๋ก๊ทธ๋๋จธ์ค
- Docker
- ์คํ๋ง๋ถํธ
- ๊ตฌํ
- ์๋ฐ
- jdbc
- pinpoint
- lombok
- ๋ฐฑ์๋
- ํ์ด์ฌ
- ๋๊ท๋ชจํธ๋ํฝ
- springboot
- java
- apm
- spring
- ํด๋ฆฐ์ฝ๋
- ์๊ณ ๋ฆฌ์ฆ
- mysql
- jpa
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |