[Programmers] 큰 수 만들기

큰 수 만들기

문제 설명

---

문제 설명

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

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

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

제한 조건

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

입출력 예

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

출처

문제 풀이

---

# 그리디 # 스택

같은 2단계 문제인(지난번에 포스팅한) ‘가장 큰 수’ 문제와 비슷한 점이 있는 것 같습니다.

사용하는 자료 구조나 알고리즘이 비슷한 것은 아니지만,

‘O(n^2^)의 완전 탐색으로는 통과할 수 없고, 규칙을 찾아 O(n) 의 시간 복잡도를 만들어야 한다’는 점에서 비슷하다고 생각합니다.

두 문제 모두 입력 길이가 각각 100,000과 1,000,000으로 십만이 이 정도의 길이를 갖는 문제에 대해서는 완전 탐색을 제쳐두고,

‘아, 문제에 만족하는 규칙을 찾아야 하는 문제구나’

라고 생각해도 무방할 것 같습니다.

이 문제는 주어진 숫자에서 k개의 자리를 제외하여, 가장 큰 수를 찾는 문제입니다.

숫자에서 가장 큰 수를 찾는 것이라면 자연스럽게 높은 자릿수 숫자가 커야한다가 떠올라야 겠죠!

우선, 먼저 실패한 코드입니다.

def solution(number, k):
  for _ in range(k):
    number = sorted([number[:i]+number[i+1:] for i in range(len(number))])[-1]
  return number

각 자릿수를 제외한 숫자들 중 가장 큰 수를 찾아 풀어보려 했지만 … O(n^2)의 시간 복잡도로 성공할리가 없죠.

따라서 우리는 스택을 사용해야 합니다.

스택은 때때로 문제 풀이의 시간 복잡도를 O(n)으로 만들어주는 아주 좋은 자료구조입니다.

예를 들면, [Programmers] 주식 가격 문제 또한 그렇습니다.

🔥수열에 있어 정해진 대소 관계(또는 순서 관계)를 따라야 할 때, 스택을 사용할 수 있습니다. 🔥

def solution(number, k):
    s = []
    for i in range(len(number)):
        while s and s[-1] < number[i]: 
            s.pop()
            k -= 1
            if k == 0: return ''.join(s + list(number[i:]))
        s.append(number[i])
    return ''.join(s)[:-k]

앞자릿수가 더 커야 한다는 규칙을 이용하여, 스택의 맨 뒤 원소가 이번에 push할 원소보다 작다면 맨 뒤 원소가 push할 원소보다 크거나 스택이 빌 때까지 원소를 pop합니다.

number의 각 자릿수를 모두 돌지 않더라도, k번의 pop이 이루어졌으면 스택 원소에 돌지 않은 자릿수들을 붙여서 반환합니다.

반대로 각 자릿수를 모두 돌았는데도 k번의 pop이 이루어지지 않았으면 k개의 스택의 뒤쪽 원소(낮은 자릿수)를 제외하고 반환합니다.

간단히 예시를 들어 설명하면 다음과 같습니다.

• number = “4177252841”, k=4

  k(pop할 횟수)	s(스택)	연산
  4	[4]	append
  4	[4, 1]	append
  3	[4]	pop
  2	[]	pop
  2	[7]	append
  2	[7, 7]	append
  2	[7, 7, 2]	append
  1	[7, 7]	pop
  1	[7, 7, 5]	append
  1	[7, 7, 5, 2]	append
  0	[7, 7, 5]	push
  0	[7, 7, 5, 8]	append

  return “775841”

• number = “999”, k=2

  k	s	연산
  2	[9]	append
  2	[9, 9]	append
  2	[9, 9, 9]	append

  return “9”