[Stack] 프로그래머스 “큰 수 만들기” Python 풀이

문제 링크

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

풀이

• 문제에 따르면, 입력 numbers에 대해서 해당 문자열이 가장 큰 수를 만들게끔 k개를 빼야 합니다.
• 예제 입력을 살펴보겠습니다.
  • numbers = "4177252841", k = 4
• 어떻게 가장 큰 수를 만들 수 있을까요?
• 먼저, 일단 숫자가 나오면 스택에 저장합니다.
• 그리고 그 숫자보다 큰 숫자가 나오면 스택에 저장했던 수를 빼보면 어떨까요?
• 자 시작해봅시다.
• 처음 숫자인 4를 넣습니다.
  • stack = ["4"] ( k = 4 )
• 그 후 1을 넣습니다. 1은 스택에 마지막으로 저장된 4보다 작기 때문에 뺄 필요가 없습니다.
  • stack = ["4", "1"] ( k = 4 )
• 이제 7을 넣습니다. 그런데, 7은 스택에 마지막으로 저장된 1 보다 크기 때문에 1을 빼줍니다.
  • stack = ["4"] ( k = 3 )
• 다시 스택에 마지막으로 저장된 4와 7을 비교합니다. 역시 7이 더 크니 4를 빼줍니다.
  • stack = [] ( k=2 )
• 이제 비교할 수 가 없으니 7을 넣습니다.
  • stack = ["7"] ( k=2 )
• 이제 다시, 7, 2 를 순서대로 넣습니다.
  • stack = ["7", "7", "2"] ( k = 2 )
• 이제 5를 넣습니다. 이때, 스택에 마지막으로 저장된 2 보다 크기 때문에 2를 빼줍니다.
  • stack = ["7", "7"] ( k = 1 )
• 이제 마지막으로 저장된 7보다 작기 때문에 빼지 않고 5를 넣습니다.
  • stack = ["7", "7", "5"] ( k = 1 )
• 이제 2를 넣습니다. 마지막으로 저장된 5보다 작기 때문에 빼기는 일어나지 않습니다.
  • stack = ["7", "7", "5", "2"] ( k = 1 )
• 이제 8을 넣습니다. 이때, 마지막으로 저장된 2 보다 크기 때문에 2를 빼줍니다.
  • stack = ["7", "7", "5"] ( k = 0 )
• 이제 더 이상 뺄 k가 없기 때문에, 8을 넣어줍니다.
  • stack = ["7", "7", "5", "8"] ( k = 0 )
• 이제 k=0 이기 때문에 뒤에 숫자들을 모두 넣어줍니다.
  • stack = ["7", "7", "5", "8", "4", "1"] ( k = 0 )
• 이 문자열들을 하나로 합쳐줍니다. 그럼 원하는 결과가 나옵니다.
  • result = "775841"
• 예를 한 번 더 살펴봅시다.
• 다음 입력이 있다고 가정해봅시다.
  • numbers = "54321", k = 2
• 5를 넣습니다.
  • stack = ["5"] ( k = 2 )
• 4를 넣습니다. 마지막으로 저장된 5보다 작기 때문에 빼기는 일어나지 않습니다.
  • stack = ["5", "4"] ( k = 2 )
• numbers를 모두 순회해도 앞 수보다 작기 때문에 결국 아래와 같은 결과가 됩니다.
  • stack = ["5", "4", "3", "2", "1"] ( k = 2 )
• 하지만, k 가 남았기 때문에, 스택의 뒤부터 k개만큼 잘라야합니다.
  • stack = ["5", "4", "3"] ( k = 0 )
• 따라서, 최종 답은 아래와 같습니다.
  • result = "543"

코드

def solution(number, k):

    # 스택 초기화
    stack = [number[0]]

    # 2번째 숫자부터 순서대로 탐색
    for i in range(1, len(number)):

        # 스택에 아직 숫자가 남아있다면, 현재 숫자가 스택의 마지막으로 저장된 숫자보다 크다면, 아직 빼기 횟수가 남아있다면
        while (stack and number[i] > stack[-1] and k > 0):
            # 스택의 마지막으로 저장된 숫자 빼기
            stack.pop()
            # 남은 빼기 횟수 감소
            k -= 1

        # 스택에 현재 숫자 삽입하기
        stack.append(number[i])

    # k가 남아있는 경우, 스택의 마지막에서 k개를 제거
    if (k != 0):
        stack = stack[:-k]

    # 결과 문자열 생성
    return ''.join(stack)

참고

• https://gurumee92.tistory.com/162