[프로그래머스] 큰 수 만들기 (Python/그리디/Greedy)

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

 

<문제 설명>

어떤 숫자에서 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