[프로그래머스] LEVEL2 큰 수 만들기,python3, 탐욕법(greedy)

1차시도(여러번 했지만 ㅋㅋ)

def solution(number, k):
    answer = ''
    front=''
    rear=''
    cnt=20
    while k>0:
        max_num=max(number)
        max_ind=number.index(max_num)
        if max_ind==0:
            front+=number[0]
            number=number[1:]
            
        if k>=max_ind:
            number=number[max_ind:]
            k-=max_ind
        else:
            rear=number[max_ind:]+rear
            number=number[:max_ind]
        
        #print("front:{}\tnumber:{}\trear:{}\tk:{}".format(front,number,rear,k))
        if number=='':
            if k==1:
                front=front[:-1]
            answer=front+number+rear
            break
        if k==0:
            answer=front+number+rear
    
    return answer

---

2차 시도

def solution(number, k):
    index=0
    while k>0:
        len_num=len(number)
        if (number[index]==number[index+1]):
            if len_num-2==index:
                number=number[:-1]
                k-=1
                index=0 
            else:
                index+=1
        elif (number[index]>number[index+1]):
            index+=1
        else:
            number=number[:index]+number[index+1:]
            k-=1    
            index=0 
        
   
    return number

런타임에러는 1010 -> 11을 해결하니까 사라졌다

---

3차시도

def solution(number, k):
    answer = ''
    stack=''
    while k!=0:
        if number!='':
            stack+=number[0]    #1
            number=number[1:]   #924
            len_stack=len(stack)
            #print("stack:{}\tnumber:{}\tlen_stack:{}\tk:{}".format(stack,number,len_stack,k))
            for i in reversed(range(len_stack)):
                #print("i:{}".format(i))
                if number=='':
                    break
                if number[0]>stack[i]:
                    stack=stack[:i]
                    k-=1
                    if k==0:
                        break
                else:
                    break
        else:
            stack=stack[:-1]
            k-=1
    answer=stack+number
    return answer

계속 같은 시도를 했었으나 며칠간 진행할수 없었다.

비교를 어떻게해야 조금더 좋게 할수있을지 고민하다 조금의 도움을 받았는데 탐욕법말고 스택으로 비교할수도 있다고 해서 짜보았더니 성공하였다.

뒤의 수가 클때 앞의 수를 하나씩 삭제하는 스택을 만든 것이다.

4177252841 이 주어지면 number[0]와 stack의 모든 수를 뒤에서부터 비교한다

stack	number	after_stack	k
4	177252841	4	4
41	77252841		2
7	7252841	7	2
77	252841	77	2
772	52841	77	1
775	2841	775	1
7752	841	775	0

k가 0이 되었을때 while문을 종료하고 그때의 stack값과 number를 더하여서 return 하면 나온다.

99999999....999999 인경우 혹은 987654321의 경우에는 number가 ' ' empty state 상태가 되어서 오류를 발생한다.

그때는 stack을 뒤에서부터 하나씩 삭제하게된다.

---

다른사람의 풀이

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

방법은 비슷하나 조금더 쉽고 효율적으로 구현했다.