ํ‹ฐ์Šคํ† ๋ฆฌ ๋ทฐ

๐Ÿ”— ๋ฌธ์ œ ๋งํฌ

https://school.programmers.co.kr/learn/courses/30/lessons/92335

 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr

 

๐Ÿ“ ํ’€์ด

์ด ๋ฌธ์ œ๋Š” ๊ฐœ๋ณ„์ ์œผ๋กœ ๊ตฌํ˜„ํ•ด์•ผํ•  ๊ฒƒ๋“ค์ด ๋งŽ์•˜๋‹ค.

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
๊ณต์ง€์‚ฌํ•ญ
์ตœ๊ทผ์— ์˜ฌ๋ผ์˜จ ๊ธ€
์ตœ๊ทผ์— ๋‹ฌ๋ฆฐ ๋Œ“๊ธ€
Total
Today
Yesterday
๋งํฌ
ยซ   2025/01   ยป
์ผ ์›” ํ™” ์ˆ˜ ๋ชฉ ๊ธˆ ํ† 
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
๊ธ€ ๋ณด๊ด€ํ•จ