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

문제

아쉬운 점

내 풀이는 현재 가장 큰 수의 위치에서 없애야 하는 것의 남은 수 를 더한 위치 까지 가장 큰수를 찾아서 그 큰 수를 다시 가장 큰수로 만드는 것이다.

그리고 각각의 가장 큰 수 들을 문자열로 더해서 반환을 하는 방법으로 하였다.

하지만, 이렇게 하는 과정에서 빼야 되는 남은 수 = 빼야되는 남은 수 - 다음 가장 큰 수 의 위치 - 현재 가장 큰 수의 위치 로 하는 것이 수식(?) 코드(?) 로 바로 안떠오른 것이 아쉬운 점이다. 이 과정속에서 코드가 복잡해졌기 때문이다.

나의 코드

  def solution(number, k):
      numbers = list([(str(x), i) for i, x in enumerate(number)])
      length = len(numbers) - k
      now = 0
      count = k
      answer = ''
      while length > 0:
          max_number = (-1, -1)
          for i in range(now, now + count + 1):
              if int(max_number[0]) < int(numbers[i][0]):
                  max_number = numbers[i]
                  if numbers[i][0] == '9':
                      break

          count -= (max_number[1] - now)
          answer += max_number[0]
          now = max_number[1] + 1
          length -= 1

      return answer

남의 코드

1. 스택을 만든다.

2. 스택에 맨 앞자리부터 숫자를 넣고, 매 숫자를 검사하며 아래의 과정을 반복한다.

   2.1. 숫자를 넣을 떄, 그 숫자가 현재 들어 있는 스택의 마지막 수 보다 큰 것이라면, 현재 들어 있는 스택의 마지막 수를 뺀다. 이 과정을 현재 들어 있는 스택을 뒤부터 확인해서 현재 숫자보다 크거나 같을 떄 까지 검사한다.

   2.2. 스택의 마지막 수를 뺐기 때문에,
   빼야 되는 갯수 - 1 을 해준다
   그리고, 현재 들어올 숫자를 넣어준다.

3. 모든 숫자를 검사하고 나서, 뺴야되는 갯수가 있다면, (999988, 2) 와 같은 예 이기 때문에,

   [999988] 이 들어있는 스택에서 남은 k 만큼 빼 주면 된다

요약

• 맨 앞자리 부터 가장 큰 수를 찾는다.
• 그 가장 큰 수 보다 큰 게 없으면 그걸 가장 큰 수로 인정 하고
• 다음 가장 큰 수를 찾는다
• 이 과정을 반복한다.

 def solution_stack(number, k):
    stack = [number[0]]
    number = number[1:]

    for num in number:
        while stack and stack[-1] < num and k > 0:
            stack.pop()
            k -= 1
        stack.append(num)
    print(stack)
    if k > 0:
        stack = stack[0:-k]

    return ''.join(stack)