[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/42883
📌문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건)
number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.입출력 예)
💡 문제 풀이
재귀로 풀었을 때 런타임과 시간초과로 실패... 이후 계속 도전하였지만 문제를 해결할 알고리즘을 생각해내지 못했다.
컴퓨팅 사고력이 아직 부족함을 느꼈다...😂
아래 코드는 다른 사람의 아이디어를 참고 후 코드로 구현한 내용이다.
step1) 스택(stack)의 자료구조를 이용하였으며 number의 첫 번째 값을 스택에 넣은 상태에서 시작!
ex) number = '32123' | stack = ['3'] | k = 2
step2) number의 두 번째 값부터는 스택의 마지막 값과 비교
- if 스택의 마지막 값 >= number[i]의 값이면 스택에 추가한다.(append)
ex) stack[-1] = 3 > number[1] = 2
stack = ['3', '2'] - else
스택에 원소가 존재하며 k > 0이고 스택의 마지막 값이 number[i] 보다 작을 경우 스택의 마지막 원소를 뺀다.(pop)
뺀 원소만큼 k를 1씩 빼준다.
ex) stack = ['3', '2', '1'] | number[3] = 2
stack[-1] = 1 < number[3] = 2
stack = ['3', '2'] | k = 1
반복문을 마쳤을 때 스택에 남아있는 값을 순서대로 하나의 문자열로 묶어주면 그 값이 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자다.
number = '32123' | k = 2의 경우 정답은 323
def solution(number, k):
answer = ''
stack = [number[0]]
while k:
for i in range(1, len(number)):
if int(stack[-1]) >= int(number[i]):
stack.append(number[i])
else:
while len(stack) and k and int(stack[-1]) < int(number[i]):
stack.pop(-1)
k -= 1
stack.append(number[i])
else:
return ''.join(stack[:len(number)-k])
return ''.join(stack)참고한 아이디어를 손코딩으로 확인하였을 때 감탄하며 놀랐다...
역시 알고리즘 문제는 많이 풀어봐야 하며 다양한 관점에서 문제를 바라봐야 한다는 것을 느꼈다. 👌 더 노력하자 😁
