문제
"어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자"
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24]를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다.
number에서 k개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한사항
-
number는 1자리 이상, 1,000,000자리 이하인 숫자
-
k는 1 이상, number의 자릿수 미만인 자연수
Solution
처음에는 number 문자열을 int형 배열로 바꾸어 준 뒤 배열의 시작점과 마지막점을 바꾸어 줘 가면서 제일 큰 수를 찾아서 답인 문자열을 만들어 나가는 방식으로 풀었다. 그런데 테스트10의 경우에만 계속 시간초과가 났다.
(시간 초과 난 코드이므로 따로 코드 설명은 없음)
그래서 stack을 이용해 풀어보았다.
숫자들을 처음부터 차례로 stack에 넣는데 stack의 가장 위에 있는 수가 넣으려고 하는 수보다 크면 그냥 넣고,
작으면 큰 값이 나올 때까지 stack에 있는 값들을 pop을 해준 뒤 stack에 넣어준다.
pop할 때마다 k를 감소시켜주고, k가 0이 되면 더 이상 삭제할 수 없으므로 남은 수를 모두 넣어준다.
수를 끝까지 다 비교했는데 아직 삭제해야 할 수인 k가 남아있으면 k의 값만큼 뒤에서부터 잘라준다.
이렇게 풀 수 있는 이유는 가장 큰 수는 앞자리 수가 크면 되기 때문에 뒤는 잘라도 상관없다
이렇게 풀었는데 또 시간초과가 났다.
알고보니 처음에 number 문자열을 int형 배열로 바꾸어 준 것이 문제였다..
굳이 int형 배열로 바꾸어주지 않아도 문자열 그대로도 충분히 해결할 수 있는 문제였다
코드 설명
#1. stack 생성
#2. number 문자열 끝까지 순회
#3. stack의 마지막 값보다 넣으려고 하는 값이 클 때
#3-1. stack의 마지막 값이 넣으려고 하는 값 보다 크다면 그냥 넣어주기
#4. 삭제할 수 있는 값이 아직 있으면 stack에서 pop하고 삭제할 수 있는 값 하나 감소
#5. 삭제할 수 있는 값 더 이상 없으면 while문 종료
#6. number문자열 끝까지 다 순회했는데 아직 삭제해야 할 갯수가 더 남아있으면
삭제해야 할 만큼 갯수만큼 stack의 제일 마지막 부분에서 pop
#7. stack의 요소들 문자열로 합쳐서 반환
Python Code (시간 초과)
Python Code (정답)
