프로그래머스 - 큰 수 만들기

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

Link

문제

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

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

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

제한 조건

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

입출력 예

number	k	return
“1924”	2	“94”
“1231234”	3	“3234”
“4177252841”	4	“775841”

풀이

탐욕법이 무엇인지 다시 복습하자면.. 선택의 순간마다 최적의 상황만을 선택하여 최종적으로 최적에 근사한 해답에 도달하고자 하는 방법이다.

매 순간 최적의 상황만을 선택하는 것이 무조건 가장 최적에 해당하는 해답이 된다는 보장은 없다.

따라서 부분의 최적해가 전체 문제의 해답이 될 수 있는 이유에 대해 생각을 잘 도출해내야한다.

이번 문제는 숫자 number가 주어졌을 때, k개의 숫자를 제거하여 만들 수 있는 가장 큰 숫자를 찾는 문제이다.

가장 큰 숫자를 만드려면 우선적으로 앞자리가 큰 수가 되어야만 한다.

만약 number의 각 자리 숫자를 하나씩 보면서 k를 제거하는 동안 큰 수만을 남긴다면 결과적으로 가장 큰 숫자를 찾을 수가 있게 된다.

4177252841을 예로 들면..

• 4를 저장
• 4와 1을 비교 -> 4가 더 크니까 그 위에 1을 저장
• 7과 1을 비교 -> 7이 더 크니까 1을 뺌, count += 1
• 7과 4를 비교 -> 7이 더 크니까 4를 뺌, count += 1, 그리고 7 저장
• 7과 7를 비교 -> 같으니까 위에 7을 저장
• 7과 2를 비교 -> 7이 더 크니까 2를 저장
• 2와 5를 비교 -> 5가 더 크니까 2를 뺌, count += 1
• 5와 7을 비교 -> 7이 더 크니까 5를 저장
• 2와 5를 비교 -> 5가 더 크니까 2를 패스, count += 1
• count가 k와 같아졌음으로 나머지 남은 숫자들은 그대로 추가

이를 코드로 옮기면 아래와 같다 (입력의 역순으로 값을 비교하므로 stack을 사용한다).

def solution(number, k):
    answer = ''
    stack = []
    count = 0
    for c in number:
        while stack and stack[-1] < c and count < k:
            stack.pop()
            count += 1
        stack.append(c)
        
    for c in stack:
        answer += c
        
    return answer

하지만 이대로 정답을 입력할 경우 몇가지 예외에 걸리게 되는데, 예를들면 number가 “00”이고 k가 1인 경우처럼 같은 수가 반복되는 경우이다.

이 경우에는 stack 최상단의 수가 다음으로 입력될 수와 같아 문제를 일으킨다.

stack안의 성분과 비교하여 k만큼 성분을 pop해야하는데 while문 반복 조건에 부합하지 않기 때문이다.

따라서 for문이 끝난 후 count가 k와 같지 않다면, 그만큼의 숫자를 제거하지 못했다는 것이기 때문에 stack에 있는 모든 숫자를 합치기전 k-count 만큼의 숫자를 제거해줘야한다.

이를 추가한 코드는 아래와 같다.

def solution(number, k):
    answer = ''
    stack = []
    count = 0
    for c in number:
        while stack and stack[-1] < c and count < k:
            stack.pop()
            count += 1
        stack.append(c)
    
    for _ in range(k-count):
        stack.pop()
    
    for c in stack:
        answer += c
        
    return answer