[프로그래머스 / python3 / level2] 큰 수 만들기

✏️ 문제 링크

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

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

 

 

✏️ 문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number / k / return

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

 

✏️ 문제 풀이

1. stack을 만든다. 

2. number을 순회한다. 

3. stack의 top이 number[i]보다 클 때 까지 pop하고 숫자를 빼는 개수를 센다. 

4. 만약 number[i]가 top보다 작으면 stack에 push한다. 

5. number을 모두 돌았는데 만약 숫자를 제거할 수 있는 개수가 남는다면 stack의 맨 뒤에서부터 남은 수 만큼 뺀다. 

 

 

 

✏️ 문제 코드

def solution(number, k):
    answer = ''
    stk = [int(number[0])]
    i=1
    cnt=0
    while i<len(number):

        if stk[-1] < int(number[i]):
            while stk and stk[-1] < int(number[i]) and cnt < k :
                cnt+=1
                
                stk.pop()
                
        stk.append(int(number[i]))
        i+=1
    
    if cnt < k :
        for i in range(k):
            stk.pop()
            
    answer = ''.join(str(s) for s in stk)
    
    return answer

 

 

✏️ 참고

https://velog.io/@dailyhyun/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%81%B0-%EC%88%98-%EB%A7%8C%EB%93%A4%EA%B8%B0

[프로그래머스] 큰 수 만들기 (python)