[Python] 프로그래머스 Lv.2 - 큰 수 만들기

programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

[ 알고리즘 ]

그리디

 

[문제 접근]

1. 앞에서 부터 큰 수가 와야한다는 점

2. 삭제되는 값이 k개 이어야한다는 점

3. "9999"와 같이 같은 수로 이루어진 문자열이 존재하는 경우를 고려

4. k개가 아직 다 삭제되지 않았는데 문자열을 모두 순회했을 경우를 고려

 

이렇게 4가지를 염두해두고 풀이한 문제이다

 

que를 이용하여 문자열을 하나씩 담아주고, 해당 문자열이 이미 que에 들어가있는 숫자보다 크다면, 즉 이미 que에 담긴 숫자가 해당 숫자보다 작다면 pop으로 삭제를 해준다. 이때 k < 0 이면 더 이상 pop을 진행하면 안되기 때문에 k==0인 경우에는 무조건 pop한 숫자를 다시 append해주었다.

 

[코드]

from collections import deque
def solution(number, k):
    que=deque()
    answer = ''
    i=1
    que.append(number[0])
    
    while True:
        #k가 0이 아닌데, 인덱스는 이미 끝남 #9999
        if k!=0 and i==len(number):
            answer=''.join(map(str,list(que)))
            answer=answer[0:-k]
            return answer
            
        if k==0:
            if i==len(number):
                break
            que.append(number[i])
            i+=1
            continue
            
        ptr=number[i]

        
        while len(que)>0:
            p=que.pop()
            if ptr<=p or k==0:
                que.append(p)
                break
            elif ptr>p and k!=0: #현재 숫자가 나머지 애들보다 큼
                k-=1                    
        
        que.append(ptr)
        i+=1

    
    answer=list(que)
                       
    return ''.join(map(str,answer))