[프로그래머스] 파이썬 _ 큰 수 만들기

https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

문제유형 : 그리디

 

문제풀이 : 

• 스택을 이용한다. ( 숫자의 맨앞을 계속해서 더 크게 만들어주는것 )
• 스택에 숫자가 있고 k가 0 이상이면 현재숫자와 비교해서 더 큰값이 스택의 앞쪽에 위치할 수 있도록 한다.
  • 만약 현재숫자가 현재스택 최상단숫자보다 작으면 그냥 넣는다.
  • 현재숫자가 더 크다면 스택에서 pop하고 k를 1감소시킨다. 이 과정을 더이상 스택의 최상단에서 현재숫자보다 큰값이 안나올때가지 반복한다.
• 숫자를 모두 확인했는데 k가 0이상이면 더 제거해야한다는 뜻이고, 이미 앞쪽에는 최대한 큰 숫자가 앞에 위치하도록 조정해 놓은것이므로 뒤에서부터 k만큼 삭제하도록한다.

 

정답코드 : 

def solution(number, k):
    answer = ''
    stack = []
    # 스택에 숫자가 있으면 현재숫자와 비교해서 현재가 더 크면 빼고 k도 -1
    # 제일 큰 숫자가 맨 앞이 되도록 조저한다.
    # 현재숫자가 더 작으면 스택에 넣는다.
    # k=0이면 그만한다.
    # k가 0이상이면 number를 줄인다.
    for i in number:
        if stack and k>0:
            # 아직 잇고 상단값이 현재값보다 작으면 계쏙반복 
            while stack and stack[-1] < i and k>0:
                stack.pop()
                k -= 1
            stack.append(i)
        else: #스택이 비어있거나 k가 0이라서 더이상 줄일수가 없을때 
            stack.append(i)    
    if k >0:
        for _ in range(k):
            stack.pop()
    
    
    return ''.join(stack)

 

 

백준의 2812번_ 크게만들기와 똑같다.

https://www.acmicpc.net/problem/2812

import sys
input = sys.stdin.readline

k,n = map(int, input().split())

number = input().strip()

s =[]

#1924
for i in number:
    if not s or n == 0: #s가 비어있으면
        s.append(i)
    else:
        while s and s[-1] < i and n>0:
            s.pop()
            n -= 1
        s.append(i)

if n>0:
    s = s[:len(s)-n]

print(''.join(s))