[프로그래머스] 큰 수 만들기 (python)

노다현·2021년 1월 1일
0

알고리즘

목록 보기
20/22
post-thumbnail

문제

"어떤 숫자에서 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 (정답)

profile
DAilyHYUN.log

0개의 댓글