[프로그래머스/파이썬] 큰 수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

그리디 문제이다

 

사실 문제 자체는 2중 for문을 쓰면 금방 풀리긴 하는데, 그렇게 호락호락 할리가 없지 ㅎㅎ

 

조건이 백만까지 주어져서, 2중 for문을 쓰면 시간초과가 뜰 것이다.

 

이 문제는 주어진 숫자들을 정렬해서 푸는 문제가 아니므로, 앞에서부터 작은 수들을 지워나가야 한다.

 

키포인트는 stack을 이용한 풀이이다.

 

숫자들을 스택에 넣다가, 만약 스택의 top보다 큰 수가 나오면 스택의 top은 '제일 큰 수'를 만드는데 걸림돌이 되는 수이므로 정답에 포함되면 안된다.

 

예를 들어, 4177252841 , k=4 라고 하자

1) stack = [], num = 4, k =4

2) stack = [4], num =1, k = 4

3) stack = [4,1], num =7, k= 4

4) stack =[7], num = 7, k=2

5) stack[7,7], num = 2, k=2

6) stack[7,7,2], num = 5, k=2

7) stack[7,7,5], num = 2, k=1

8) stack[7,7,5,2], num = 8, k=1

9) stack[7,7,5,8], num = 4, k=0

10) stack[7,7,5,8,4], num = 1, k=0

11) stack[7,7,5,8,4,1], end, k=0

 

이 순서를 하나씩 따라가다 보면 감이 올 것이다.

 

유의할 점!

ex) 4321, k=2 같은 경우는 어떻게 할까..?

=> answer = ''.join(arr[:len(arr)-k]) 를 잘 살펴보자

def solution(number, k):
    answer = ''
    arr = []

    for num in number:
        if k > 0:
            if len(arr)==0:
                arr.append(num)
            else:
                while len(arr)>0 and arr[-1] < num and k>0:
                    arr.pop()
                    k-=1
                arr.append(num)

        else: arr.append(num)
                         
    answer = ''.join(arr[:len(arr)-k])
    return answer