πŸ“ PROGRAMMERS - 큰 수 λ§Œλ“€κΈ°

문제

PROGRAMMERS Level 2 - 큰 수 λ§Œλ“€κΈ°

μ ‘κ·Ό 방법

이 λ¬Έμ œλŠ” μ–΄λ–€ 숫자 NN이 μ£Όμ–΄μ‘Œμ„ λ•Œ kk개 만큼의 숫자λ₯Ό μ œκ±°ν–ˆμ„ λ•Œ λ§Œλ“€ 수 μžˆλŠ” 수 쀑 κ°€μž₯ 큰 수λ₯Ό λ°˜ν™˜ν•˜λŠ” λ¬Έμ œμ΄λ‹€.

잘λͺ»λœ μ ‘κ·Ό - 숫자λ₯Ό μ œκ±°ν•˜μž

μ²˜μŒμ—λŠ” 문제 μžˆλŠ” κ·ΈλŒ€λ‘œ μ–΄λ–€ 수λ₯Ό λΉΌμ•Ό κ°€μž₯ 큰 μˆ˜κ°€ 될까λ₯Ό μƒκ°ν–ˆλ‹€. κ·Έλž˜μ„œ κ°€μž₯ μ²˜μŒμ— μžˆλŠ” μˆ˜μ™€ κ·Έ λ‹€μŒ μˆ˜λ“€ 쀑 κ°€μž₯ μž‘μ€ μˆ˜μ™€ 비ꡐ해 κ°€μž₯ μž‘μ€ 수λ₯Ό μ œκ±°ν–ˆλ‹€. ν•˜μ§€λ§Œ 47712394μ—μ„œ 3개λ₯Ό μ œκ±°ν•œλ‹€κ³  ν•  λ•Œ κ°€μž₯ 큰 μˆ˜λŠ” 77394인데 μœ„μ˜ μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ μ œκ±°ν•˜λ©΄ 47794κ°€ λœλ‹€.

μ˜¬λ°”λ₯Έ μ ‘κ·Ό - 숫자λ₯Ό λ„£μž

κ²°κ΅­ λ‹€λ₯Έ λΆ„λ“€μ˜ 풀이λ₯Ό μ°Έκ³ ν–ˆλŠ”λ° 숫자λ₯Ό μ œκ±°ν•˜λŠ” 것이 μ•„λ‹Œ 숫자λ₯Ό ν•˜λ‚˜μ”© 넣어보며 μ ‘κ·Όν–ˆλ‹€. 주어진 숫자의 κ°€μž₯ μ•ž μžλ¦¬λΆ€ν„° μˆœνšŒν•˜λ©΄μ„œ μ΅œμ’… κ²°κ³Όλ₯Ό stack에 μ €μž₯ν•˜λŠ”λ° λ‹€μŒκ³Ό 같은 κ·œμΉ™μ„ κ°–κ³  μˆœνšŒν•œλ‹€.

  • stack의 탑(top)에 μžˆλŠ” 숫자 < μˆœνšŒν•˜κ³  μžˆλŠ” 숫자이고 kλ₯Ό λ‹€ μ†Œμ§„ν•˜μ§€ μ•Šμ•˜λ‹€λ©΄

    • μˆœνšŒν•˜κ³  μžˆλŠ” μˆ«μžλ³΄λ‹€ 큰 μˆ«μžκ°€ λ‚˜μ˜¬ λ•ŒκΉŒμ§€ stack을 popν•œλ‹€.
    • popν•œ 횟수만큼 kλ₯Ό μ†Œμ§„ν•œλ‹€.
  • μˆœνšŒν•˜κ³  μžˆλŠ” 숫자λ₯Ό stack에 λ„£λŠ”λ‹€.
  • λ‹€ μˆœνšŒν•˜κ³ λ„ kλ₯Ό λ‹€ μ†Œμ§„ν•˜μ§€ λͺ»ν–ˆλ‹€λ©΄ stack의 μœ„μ—μ„œ kλ§ŒνΌμ„ μ œκ±°ν•΄μ€€λ‹€.

κ΅ν›ˆ

κ·Έλ¦¬λ””λŠ” ν˜„μž¬ μƒνƒœμ—μ„œ μ΅œμ„ μ˜ 선택을 ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜μΈλ° ν˜„μž¬μ˜ μ΅œμ„ μ˜ 선택이 졜고의 선택이 λœλ‹€λŠ” 보μž₯이 μ—†λ‹€. κ·ΈλŸ¬λ―€λ‘œ μ΅œμ ν•΄λ₯Ό 보μž₯ν•˜λŠ”μ§€λ₯Ό κ³ λ €ν•΄μ•Όν•˜λŠ”λ°.. 말은 이렇고 사싀 아직 그리디λ₯Ό λͺ¨λ₯΄κ² λ‹€γ… γ… 

λ™μ κ³„νšλ²•μ²˜λŸΌ 많이 풀어봐야 감을 읡힐 수 μžˆμ„ 것 κ°™λ‹€.

μ†ŒμŠ€ μ½”λ“œ

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        # λ„£μœΌλ €λŠ” num이 stack의 top보닀 크닀면
        # stack의 top이 num보닀 클 λ•ŒκΉŒμ§€ stack을 popν•œλ‹€.
        while len(stack) and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        # λ‹€ popν•˜κ³  λ‚œ λ’€ num을 λ„£μ–΄μ€€λ‹€.
        stack.append(num)
    # λ‹€ μˆœνšŒν•˜κ³  kκ°€ λ‹€ μ†Œμ§„λ˜μ§€ μ•Šμ•˜λ‹€λ©΄
    # stack의 μœ„μ—μ„œ kλ§ŒνΌμ„ μ œκ±°ν•΄μ€€λ‹€.
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

Written by@μ½”λ”©ν•˜λŠ”νŽ­κ·„
μ§€κΈˆμ€ ν•˜κ³  싢을 λ•Œλ§Œ κ³΅λΆ€ν•©λ‹ˆλ‹€πŸ€—

GitHubInstagramAI Notebook