❓ 문제
문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한사항
- number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다
입출력 예
🔎 문제 분석
- 큰 수를 만드는 원칙은 무엇인가?
- 앞 자리에 큰 수가 오는 것이 전체를 크게 만든다.
- 그래서 우리는 큰 것을 우선해서 골라 담아야 한다.
- 어떻게 풀어야 할까?
- 앞 자리에서부터 하나씩 골라서 담지만
지금 담으려고 하는 것보다 작은 것이 나오면 뺀다. k개까지만이 과정을 반복한다.- 큰 수가 앞에 작은 수가 뒤에 나오기만 하면 된다.
- 아직 뺄 개수(k)를 채우지 못한 경우 제일 끝에서 몇 개를 덜어내야 하는데 이때 자릿수를 어떻게 계산해야 하는가?
- 앞 자리에서부터 하나씩 골라서 담지만
- 이 알고리즘은 복잡도가 어떻게 될까?
O(n)-> 더해지는 것도 빠지는 것도 모두 한 번이기 때문에
탐욕법에 의한 알고리즘을 사용할 수 있는가?
-앞 단계에서의 선택(앞자리에 큰 수)이이후 단계에서의 동작에 의한 해의 최적성에 영향을 주지 않는다.
❗ 풀이
- 쌓여 있는 숫자들을 뒤에
stack을 이용해서number의 원소를 쌓는다. - 다만
stack의 마지막 원소가 비교하는 값보다 작고, 횟수가k번을 초과하지 않은 경우k횟수를 1 회 줄이고stack의 마지막 값을pop으로 꺼내 제거한다. - 모든 while 문을 다 돈 후 k가 0이 아닐 때, 즉 뺄 수 있는 값을 모두 뺐지만 빼야 할 횟수가 남아 있을 경우
리스트 슬라이싱하여 처리해 준다.
def solution(number, k):
answer = ''
stack = []
for num in number:
while stack and stack[-1] < num and k > 0:
k -= 1
stack.pop()
stack.append(num)
if k != 0:
stack = stack[:-k]
answer = ''.join(stack)
return answer❕ 다른 사람의 풀이
- 내 풀이에서 크게 달라진 것이 있다면
for 문에서index역시 같이 체크하게 만들어 주었고k 번제거를 끝낸 경우 collected에 확인하지 않은index이후의 값을 추가해 주고for문을 빠져나가게 처리해 주었다. while과for같은 반복문에서는 모든 행위가 끝났을 때 의미 없는 반복을 하지 않도록 처리해 주는 게 시간적 효율을 따졌을 때 유리하다.
def solution(number, k):
collected = []
for i, num in enumerate(number):
#아직까지 k>0 빼낼 개수가 남아 있으면서 마지막 글자가 num보다 작은 거로 비교해야 하지만
#이때 collected 배열에 원소가 없다면 오류가 발생함으로 이 부분도 처리해 줌.
while len(collected) > 0 and collected[-1] < num and k > 0:
collected.pop()
k -= 1
if k == 0:
collected += list(number[i:])
break
collected.append(num)
collected = collected[:-k] if k > 0 else collected
answer = ''.join(collected)
return answer
송의 개발 LOG