[프로그래머스] - 큰 수 만들기

문제이해

파라미터로 전달된 숫자에서 k개의 수를 제거하여 가장 큰 수 로 만드는 문제이다.

---

문제생각

나는 stack 자료구조를 이요하면 가능하다고 생각했다. 

왜냐하면 해당 문제는 앞의 숫자를 그 이전의 숫자와 비교해야하기 때문이다.

위의 이유때문에 LIFO(Last In First Out)의 스택을 사용하면 현재 숫자와 이전 순서에서 나온 숫자와의 비교와 제거가 쉽다고 생각했다.

---

문제풀이

1. 앞의 숫자부터 순차적으로 반복문을 돌린다.

2. 스택이 비어있다면 값을 넣는다.

3. 그렇지 않다면 while 문을 돌리는데 이 while문에서는 앞의 숫자와의 비교를 실행한다.

- 만약 앞에 출현한 숫자가 현재 나온 숫자보다 작다면 더 작은 수가 된다.

- 따라서 앞의 나온 숫자를 스택에서 pop()해주고 k(제거할 수의 개수)를 -1 해준다.

- while문은 k가 0이 되기전까지 반복한다.

- 만약 스택이 비었거나, 앞의 나온숫자가 현재 나온 숫자보다 크거나 같다면 break

- 현재 나온숫자를 append()한다.

 

위의 순서로 코드를 작성하였다.

 

근데 위의 동작은 하나의 예외가 있다.

만약 전달된 숫자가 54321, k=1 이라면?

 

현재 나온 숫자가 앞에 나온숫자보다 무조건 작기때문에 스택에 append()만 되고 pop()은 되지 않는다.

따라서 마지막에 k값을 확인하여 스택의 뒤에서 부터 k만큼 값을 잘라줘야한다.

---

문제코드

def solution(number, k):
    answer = []
    for n in list(number):
        if len(answer)==0:
            answer.append(n)
        else:
            while k!=0:
                if len(answer)==0 or answer[-1]>=n:
                    break
                if answer[-1]<n:
                    answer.pop()
                    k-=1
            answer.append(n)
    
    if k!=0:
        answer=answer[:len(answer)-k]
    return ''.join(answer)