[프로그래머스] 큰 수 만들기 / Python
문제주소 :programmers.co.kr/learn/courses/30/lessons/42883#
코딩테스트 연습 - 큰 수 만들기
programmers.co.kr
<문제 설명>
문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
- number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상number의 자릿수미만인 자연수입니다.
입출력 예
number k return
| 1924 | 2 | 94 |
| 1231234 | 3 | 3234 |
| 4177252841 | 4 | 775841 |
<풀이법>
▒ 한줄 개념: 탐욕법 *▒ *
이 문제의 핵심은 탐욕법입니다. 현재 상황에서 가장 좋은 값을 챙긴다는 뜻이죠.
이 문제의 해결 방향을 살펴보면 다음과 같습니다.
number = "4177252841"
k = 4
i = 0 -> number를 탐색하는 인덱스
checked = [] -> 스택 배열
문제의 3번째 예시를 이용해서 설명해보겠습니다.
여러가지 수들 중 가장 큰 수는 앞자리의 수가 큰 수가 됩니다.천 단위 숫자이면 천의 자리 수가, 백 단위의 숫자이면 백의 자리수가 가장 커야한다는 뜻입니다.탐욕법을 이용해 이 풀이를 구현하는 방법은, number의 맨 앞부터 시작해서 한 글자 한 글자 탐색해나가며 큰 수들만 남기고 작은 수는 삭제하는 것입니다.
----시작(i =0)----
k = 4
number[i] = 4
checked = []
changed_checked = ['4']
처음 탐색을 시작하면 상태는 위와 같습니다. checked에 어떤 값도 없으니 일단 0번째 숫자인 4를 넣습니다.
---- i = 1 ----
k = 4
number[i] = 1
checked = ['4']
changed_checked = ['4', '1']
현재 checked엔 4가 들어가있고, 이번에 가져온 숫자는 1입니다. 1과 checked의 맨 뒤 숫자인 4를 비교하면, 4가 더 큽니다. 따라서 1을 그냥 넣습니다.
---- i = 2 ----
k = 4
number[i] = 7
checked = ['4', '1']
changed_checked = ['4']
현재 checked엔 4,1이 들어가있고, 이번에 가져온 숫자는 7입니다.
7과 checked의 맨 뒤 숫자인 1을 비교합니다. 7이 더 큽니다. 그럼 1은 pop됩니다.
숫자 하나가 삭제되었으니, k값이 1 감소합니다.
---- i = 2 ----
k = 3
number[i] = 7
checked = ['4']
changed_checked = []
1이 pop 됐으니, checked엔 4만 남았습니다. 이번엔 4를 7과 비교합니다. 마찬가지로 7이 더 크니, 4 또한 pop 됩니다.
숫자가 또 삭제되었으니, k값이 또 1 감소합니다.
---- i = 2 ----
k = 2
number[i] = 7
checked = []
changed_checked = ['7']
이제 checked는 비었습니다. 따라서 7을 넣습니다.
---- i = 3 ----
k = 2
number[i] = 7
checked = ['7']
changed_checked = ['7', '7']
다음으로 가져오는 수 또한 7입니다. 가져온 7은 checked에 저장된 맨 뒤 수인 7 보다 크지 않습니다. 따라서 그냥 넣어줍니다.
---- i = 4 ----
k = 2
number[i] = 2
checked = ['7', '7']
changed_checked = ['7', '7', '2']
이번에는 2를 가져옵니다. checked의 맨 뒤 숫자인 7보다 크지 않습니다. 넣어줍니다.
---- i = 5 ----
k = 2
number[i] = 5
checked = ['7', '7', '2']
changed_checked = ['7', '7']
이번에 가져온 숫자는 5입니다. 5는 checked의 맨 뒤인 2보다 큽니다. 따라서, 2를 checked에서 pop해줍니다.
숫자가 삭제되었으니, k값이 1 감소합니다.
---- i = 5 ----
k = 1
number[i] = 5
checked = ['7', '7']
changed_checked = ['7', '7', '5']
그 다음에 5가 비교할 값은 7입니다. 5는 7보다 크지 않습니다. 따라서 checked에 넣어줍니다.
---- i = 6 ----
k = 1
number[i] = 2
checked = ['7', '7', '5']
changed_checked = ['7', '7', '5', '2']
이번에 가져온 값은 2입니다. 비교할 값은 5인데, 2는 5보다 작습니다. 따라서 넣어줍니다.
---- i = 7 ----
k = 1
number[i] = 8
checked = ['7', '7', '5', '2']
changed_checked = ['7', '7', '5']
이번에는 8을 가져왔습니다. 8은 checked의 마지막 값, 2보다 큽니다. 따라서 2가 pop됩니다.
2가 삭제되면서, k는 1 감소합니다.
k = 0
checked = ['7', '7', '5']
남은 number = ['8', '4', '1']
k가 0이 되었으니, 더 이상은 원소가 삭제되지 않습니다. 따라서 남은 모든 number를 checked에 붙여줍니다. 그럼 결과적으로 가장 큰 수가 나오는 것입니다.
<코드(Python)>
def solution(number, k):
checked = []
i = 0
while i < len(number) and k > 0:
if len(checked) != 0 and int(checked[-1]) < int(number[i]):
checked.pop(-1)
k -= 1
else:
checked.append(number[i])
i += 1
answer = "".join(checked) + number[i:]
if k != 0:
answer = answer[:-k]
return answer
더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest