[프로그래머스 | 레벨2] 큰 수 만들기(그리디, 숫자 제거해서 큰수만들기)

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는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예numberkreturn

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

 

문제풀이

스트링으로 들어온 숫를 k개 만큼만 제거해서 큰 숫자 만들기

숫자 뒤섞기 x

자리 유지하면서 k개 만큼만 숫자 제거

 

 

문제풀이

어떻게 가장 큰 수를 만들 수 있을까

먼저, 일단 숫자가 나오면 저장합니다. 그리고 그 보다 큰 숫자가 나오면 그보다 작았던 수들은 뺍니다.

이런식으로 풀어도 되는 이유는 

"앞자리 숫자가 가장 큰 수가 큰 수"이기 때문입니다. 

문자열 어느 부분을 쪼갠다 하더라도, 앞자리가 높은 수가 되게끔 뽑으면, 무조건 높은 숫자가 된다는 것이죠. 

즉, "앞자리를 최고 큰 수로 만들기 전략"이 부분해를 만족함과 동시에 전체의 해가 될 수 있는 것이지요.

 

참고

https://gurumee92.tistory.com/162

프로그래머스 문제 풀이 큰 수 만들기

전체코드

def solution(number, k):
    stack = []
    
    for num in number :
        #스택의 꼭대기보다 비교 숫자가 크다면
        while stack and k > 0 and stack[-1] < num: 
            #스택의 맨 위 값을 제거하고 뽑는 개수 k도 -1
            stack.pop()
            k -= 1
        #현재 num 값은 무조건 스택에 추가
        stack.append(num)
    return "".join(stack[:len(number)-k])

#숫자스트링에서 k개의 숫자를 제거했을때 가장 큰 수 만들기
#앞자리를 최고 큰 수로 만들기 전략

#1924에서 2개 삭제 1, 9, 2, 4 <<--- 1, 2 제거 
#큰 수 94

#1231234에서 3개 삭제 1, 2, 3, 1, 2, 3, 4 <<--- 1, 2, 1 제거
#큰수 3234

#4177252841에서 4개 삭제 4, 1, 7, 7, 2, 5, 2, 8, 4, 1 <<--- 4,1,2,2 제거
#큰수 775841