프로그래머스 2단계 "큰 수 만들기"

문제

프로그래머스 '큰 수 만들기'

풀이

그리디 알고리즘을 이용하여 문제를 풀었다.

answer문자열을 스택처럼 사용하여 number의 숫자를 하나씩 넣어주며 반복을 한다.
이 때 전에 들어갔던 문자열 answer[-1]이 number[i]보다 작을 경우 answer[-1]을 answer에서 빼준다.

이러한 연산을 answer[-1]이 number[i]보다 크거나 같을 때 까지 반복하며 한번의 연산마다 count의 값을 1씩 올려주고, 전체 반복에서 통틀어 k번의 연산이 진행되어야 한다.
(즉, count < k일 때만 문자열을 빼주는 것이다)

한가지 주의해야 할 건 '5555'같은 수나 내림차순인 '4321' 같은 수는 위와 같은 연산을 실행하지 않고 문자열을 넣어주기만 하여 결과가 그대로인 경우가 있다.
이를 방지하기 위해 count값이 k보다 작은 경우 answer에서 k-count만큼 뒷자리를 빼주어야 한다.
(앞자리 수 부터 큰 수만 골라 채워넣었기 때문에 뒷자리를 제거하는 것)

Python 코드

def solution(number, k):
  num = str(number)
  count = 0
  # 문자열 스택
  answer = ''
  for x in num:
    # 인접한 수가 현재 들어가는 수보다 작을 경우 인접한 수 제거
    while answer and count < k and answer[-1] < x:
      answer = answer[:-1]
      # 여태 얼마나 빼주었는지 확인하기 위해 count += 1
      count += 1

    # 숫자 추가
    answer += x
  
  # k값 만큼 빼주지 못했을 경우 더 빼주어야 하는 만큼 뒷자리 제거
  return answer if count == k else answer[:-(k-count)]