[프로그래머스] 큰 수 만들기 / Python

문제주소 :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의 자릿수미만인 자연수입니다.

입출력 예

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