문제 : 프로그래머스 큰 수 만들기
<문제 설명>
어떤 숫자에서 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" |
<문제 풀이>
그리디 알고리즘
그리디 알고리즘을 연습하기 위해서 어떻게 적용할지 고민했습니다.
우선 입력받은 숫자에서 가장 큰 수를 만들기 위해서는 가장 앞에 있는 수가 큰 수여야 합니다.
맨 앞의 수가 큰 수가 될 수 있도록 k개의 수를 제거하면서
현재까지 저장되는 수가 가장 큰 수가 되게 합니다.
만약 리스트 끝가지 갔을 때 더 제거해야 할 수가 남았다면 리스트 뒤에서 부터 제거해줍니다.
더 자세히 설명하자면
저는 우선 입력을 리스트로 변환하고
result 리스트를 만들어 결과를 저장했습니다.
입력받은 numbers를 하나씩 확인하면서 result리스트 맨 뒤에 추가합니다.
이때 현재의 numbers 요소와 그 이전 요소인 result 리스트 맨 뒤 요소의 대소를 비교합니다.
만약 이전 요소가 현재 요소보다 크다면
->result에 현재 요소를 저장하고
그렇지 않다면
이전 요소를 제거하고 현재 요소만 저장합니다.
제거한 뒤 리스트에 남은 그 이전 요소도 같은 방식으로 현재 요소와 비교합니다
k개의 수가 모두 제거 되었다면 더 이상 제거하는 작업은 하지 않고 그대로 요소를 저장합니다.
그리고 반복이 끝난 시점에서 아직 수가 k번 제거되지 않은 경우
결과의 맨 뒤부터 순서대로 제거했습니다.
<Pseudo Code>
입력 받은 numbers를 리스트로 저장
result = number의 첫번째 요소를 꺼내어 result에 저장
for n in number
if 이전 요소(result의 마지막 요소) 가 현재 요소보다 작다면
while 이전 요소가 남아있음 and 이전 요소(result의 마지막 요소)< 현재 요소 and 아직 k개의 수가 제거 안됨
결과의 마지막 요소 제거
k -= 1
elif 이미 k개의 수가 제거됨 또는 이전 요소(result의 마지막 요소)가 현재 요소보다 큼
결과에 현재 요소 추가
if 아직 k개의 수가 제거 안된 경우
result의 뒤 부터 제거
<Python Code>
def solution(number, k):
number =list(number)
result=[number.pop(0)]
for n in number:
if result[-1] < n:
while result and result[-1] < n and k>0:
result.pop()
k -= 1
result.append(n)
elif k == 0 or result[-1] >= n:
result.append(n)
if k :
result=result[:-k]
answer = ''.join(result)
return answer
