[Level 2] 큰 수 만들기

programmers.co.kr/learn/courses/30/lessons/42883?language=python3

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

---

접근

프로그래밍적으로 어떻게 풀 수 있을까가 아닌 그냥 어떻게 풀지만 생각하여 적당한 방법이 떠오르지 않았다.

그래서 다른 사람들의 풀이를 참고하였다.

그리디 알고리즘으로 분류가 되어있었고 어떠한 기준으로 최적을 선택할지 고민을 했었다. 

이럴때 앞에서부터 탐색하면서 어떻게 최적의 해를 구할지 손으로 풀어가면서 생각을 발전시킬 필요가 있다.

 

스택을 활용하여 스택에 첫 숫자를 넣어주고 시작한다

두 번째 숫자부터 탐색을 진행한다. 이때 스택의 top과 계속 비교하여 top이 더작고 제거할 수인 k가 남아있다면 계속해서 pop을 한다. 즉 앞에서부터 탐색을하여 k개를 제거하기 전까지 스택에 최적의 해를 쌓아가도록 한다.

 

구현

- for문으로 두 번째 숫자부터 탐색을 진행한다.

- 현재 나오는 수가 스택의 top보다 크고 제거할 k개 남아있다면 계속해서 pop을 하고 k를 지워준다.

- 또한 스택이 비게되도 while문을 빠져나온다.

- 위의 조건이 아니라면 계속해서 stack에 수를 넣어준다.

- 스택의 top과 비교하여 작거나 같아 제거하지 못하고 그대로 추가했을 때 뒤에서 k개를 제거하도록 한다.

def solution(number, k):
    answer = ''
    stack = []
    stack.append(number[0])
    for idx in range(1, len(number)):
        # 스택에 비어있지 않고, top이 더작고, k가 0이 아니라면
        # 계속 pop
        while stack and k > 0 and stack[-1] < number[idx]:
            k -= 1
            stack.pop()
        # 위의 while문에 의해 자기보다 작은 수들을 제거하여
        # 맨 앞에 큰 수가 오게된다.
        stack.append(number[idx])
    # 위에서 k개를 모두 제거하지 못했다면 뒤에서 k개를 제거하도록 한다.
    if k!=0:
        stack = stack[:-k]
    answer = ''.join(stack)
    return answer