[파이썬] 프로그래머스 Level.2 | 탐욕법(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의 자릿수 미만인 자연수입니다.

입출력 예

answer	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"
"10000"	2	"100"

 

---

풀이

이 문제는 어떻게 하면 런타임에러를 없앨지, 시간복잡도에 대한 고려를 요구하는 문제였다. 

처음엔 시간복잡도를 크게 신경쓰지 않고 다음과 같이 풀었더니 테스트케이스 8,10번에서 런타임에러가 떴다. 

혹시 12번에서 틀렸다고 나올 경우, 입출력 예시의 "10000",2 를 넣어보길 바란다.

 

 

def solution(number, k):
    answer = ''
    alist=[]
    nlist=list(number) 
    
    remove=0
    j=-1
    for i in range(len(nlist)):
        alist.append(nlist[i])
        j+=1
        temp=j
        if k!=remove:
            while temp!=0:   
                if alist[j-1]<alist[j] and remove!=k:
                    alist[j-1]=alist[j]
                    alist.pop()
                    j-=1
                    temp-=1
                    remove+=1
                else:
                    temp-=1
                    
    if len(alist) > len(nlist)-k:
        while len(alist)!=len(nlist)-k:
            alist.pop()
            
    answer="".join(alist)
    
    return answer

아래는 보다 효율적인 코드이다. alist[-1]가 리스트의 마지막 원소를 가리킨다는 점을 항상 생각해두자.

if문은 "10000",2 과 같은 상황을 처리하기 위해 넣은 코드이다. 

 

def solution(number, k):
    alist = [number[0]]
    for num in number[1:]:
        while len(alist) > 0 and alist[-1] < num and k > 0: 
        #바꾸는 경우- 새로들어온수가 기존수보다 크거나, k가 0이 안됐거나, alist 0개가 아닐때 
            k -= 1
            alist.pop()
        alist.append(num) #항상 append
    if k != 0: #for문 다 돌았는데 k가 안찼을때 
        alist = alist[:-k]
    return ''.join(alist)