42883. 큰 수 만들기 / python / 커뮤러닝 5기 코딩테스트 실력 UP 패키지 : 문제 풀이 꿀팁과 실전 모의고사
코딩테스트 연습 - 큰 수 만들기
programmers.co.kr
문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24]를 만들 수 있습니다. 이 중 가장 큰 숫자는 94입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건- number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
| "1924" | 2 | "94" |
| "1231234" | 3 | "3234" |
| "4177252841" | 4 | "775841" |
풀이
def solution(number, k):
number=list(number)
stack=[]
stack.append(number.pop(0))
while k>0:
num=number.pop(0)
if num<=stack[-1]:
stack.append(num)
else:
while stack and stack[-1]<num and k>0:
stack.pop()
k-=1
stack.append(num)
return ''.join(stack+number)스택을 하나 만들어 number를 숫자 앞에서 부터 하나씩 빼서 스택에 push 한다. 그리고 스택의 최상단의 값과 number에서 하나씩 뽑은 값을 비교해 스택의 최상단의 값이 작으면 제거한다. 이때 제거하는 수만큼 k에서 -1씩 하고 k개만큼 숫자를 빼면 종료한다.
테스트 10은 시간 초과로 실패하고 테스트 12는 런타임 에러가 났다.
테스트 12 런타임 에러 해결 : 만약 처음에 주어진 수가 87654321처럼 앞자리가 늘 큰 수면 위의 코드에서 런타임 에러가 난다. k가 감소하는 경우에 걸리지 않기 때문이다. 그러므로 k>0이고 number에 pop()할 거리가 남아있을 때까지만 while문을 돌리고 만약 while문 이후에서 k가 0보다 크다면 맨 뒷 수를 k개만큼 빼주면 된다
수정된 코드
def solution(number, k):
number=list(number)
stack=[]
stack.append(number.pop(0))
while k>0 and number:
num=number.pop(0)
if num==9:
stack.append(num)
continue
if num<=stack[-1]:
stack.append(num)
else:
while stack and stack[-1]<num and k>0:
stack.pop()
k-=1
stack.append(num)
stack=stack+number
while k>0:
stack.pop()
k-=1
return ''.join(stack)
테스트 10 해결 : 우선 구글링을 한 결과 테스트 10은 숫자가 9인 경우 바로 추가하고 다음 단계로 가야 한다고 했다. 위의 코드에도 그렇게 하도록 했는데 안된 걸 보면 내 코드에 군더더기가 좀 많았나 보다. 그래서 좀 더 고심해서 깔끔하게 코드를 손 봐주었다. 우선 마지막에 k가 0보다 클 경우 어차피 숫자 뒷부분을 잘라내줄 것이므로 차라리 number 전체를 순회하는 것이 더 나을 것이라고 생각되었다. 전체 while 문을 그냥 for문으로 변경하고 그에 맞게 내부 코드도 수정해 주었다.
def solution(number, k):
stack=[]
for n in number:
if n==9:
stack.append(n)
continue
while stack and stack[-1]<n and k:
stack.pop()
k-=1
stack.append(n)
while k:
stack.pop()
k-=1
return ''.join(stack)