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

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42883

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

---

문제 설명

- number: 문자열 형식의 숫자

- k: 제거할 숫자의 개수

numbers에서 k개의 수를 제거 했을 때 나올 수 있는 가장 큰 숫자를 문자열 형태로 return해주면 됩니다.

ex)

number = "12341234"  k = 3일 때 121을 제거해 3234가 최대값이 되어 정답이 됩니다.

---

풀이

stack을 활용한 문제입니다.

모든 조합을 끄내서 검사할 경우 시간초과가 나올 것입니다.

stack에 가장 높은 숫자만 남아있도록 pop을 해주는 식으로 작업합니다. 이 때 k 변수를 통해서 삭제(pop)해야하는 개수를 관리합니다.

k가 0이되면 그대로 스택에 쌓이는 구조입니다. 만약에 k가 0이 아닐경우는 아직 숫자를 전부 제거 못한경우로 잘라주어야 합니다. 

 

코드

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)

    # 마지막 테스트 케이스
    # 제거 횟수를 다 사용하지 못하면 stack에서 나머지 짤라줌
    if k != 0: 
        stack = stack[:-k]

    return ''.join(stack)