[프로그래머스] 그리디 - 큰 수 만들기

문제 <큰 수 만들기>

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

---

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

---

입출력

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

---

풀이

• 가장 쉽게 떠올릴 수 있는 것은 k개의 숫자를 제외한 숫자의 조합을 구하는 것이었다.
• 해당 숫자의 조합을 구해 내림차순 정렬했을 때 제일 처음의 인덱스의 숫자 조합이 만들 수 있는 숫자의 최댓값이다.

from itertools import combinations

def solution(number, k):
    n = list(map(int, str(number)))
    d = list(combinations(n, len(n) - k))
    d.sort(reverse=True)
    result = ''
    for i in d[0]:
        result += str(i)
    return result

해당 코드는 가장 쉽게 생각할 수 있지만, 조합을 구하는 과정에서 시간 초과가 발생한다.

조합을 이용하지 않고 가장 큰 숫자를 구하는 방법을 생각하기 위해 가장 큰 자릿수의 숫자가 최대가 되어야 한다는 것에 주목하였다.

따라서 k의 값을 이용해 숫자의 처음부터 k개까지 숫자를 비교하여 가장 큰 숫자를 택하고 택한 숫자의 이전 숫자들을 제거하는 방법으로 구현하고자 하였다.

이후 제거한 숫자의 개수만큼 k의 값을 줄이고 택한 숫자 다음의 인덱스부터 해당 과정을 반복하는 코드를 작성하였다.

• 테스트 하나를 시간초과로 통과하지 못했는데, 이는 범위 내에서 가장 큰 숫자를 찾을 때 숫자가 9일 경우 break하는 것으로 해결할 수 있었다.

def solution(number, k):
  number = list(map(int, str(number)))
  a = 0
  result = ''
  while a < len(number):  
      inx = a
      for j in range(a, a+1+k):   # number[a] ~ number[a+k]
          if number[j] == 9:      # 9는 가장 큰 숫자
              inx = j
              break
          if number[j] > number[inx]:     # 큰 숫자 갱신하기
              inx = j
      result += str(number[inx]) 
      k -= (inx-a)    # 제거한 숫자의 개수만큼 k값 줄이기
      a = inx+1       # 다음 인덱스부터 탐색
      if k == len(number) - a:    # 남은 숫자와 제거해야 하는 숫자가 같다면 break
          break
  return result

해당 풀이로 테스트를 모두 통과할 수 있었지만, 더 나은 구현 방법을 찾아보고 스택을 이용한 방법으로 풀이를 구현해 보았다.

스택을 이용한 방법은 현재 수를 스택에 넣고, 다음 수가 현재 수보다 크고 k > 0인 경우(숫자를 제거해야 할 경우) pop하는 방식이었다.

def solution(number, k):
    answer = []
    for num in number:
        if answer and k > 0 and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
    return ''.join(answer[:len(answer) - k])

이 방법은 먼저 구현했던 코드보다 직관적이고 한눈에 파악하기 수월했다.

해당 문제를 통해, 알고리즘 문제를 푸는 과정에 있어 스택이 단독으로도 충분히 효율적으로 이용될 수 있다는 것을 알았다!

---

리스트로 구현했을 때 시간 복잡도가 큰 문제는 스택, 큐로 구현할 수 있는지 판단해보자!

 

 

 

 

프로그래머스