[ 프로그래머스 ] level 2 큰 수 만들기 - 파이썬

프로그래머스 level 2 탐욕법(Greedy) 문제를 설명한다. 코딩테스트 연습은 매번 python3를 기준으로 작성한다. 

 

[ 문제 설명 ]

 

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

1924	2	94
1231234	3	3234
4177252841	4	775841

 

문제를 이해하기는 어렵지 않다. k개 만큼의 숫자를 빼서 가장 큰 수를 만들면 되는 문제이다. 

 

이 문제를 풀기 위해서 다양한 방법을 시도해보았는데.. 

이것도 런타임 에러

이것도 런타임 에러

다 런타임 에러가 났다... 

 

이거 짜는 것만으로도 머리를 엄청 썼는데ㅠㅠㅠ

 

우선 이 문제를 풀기 위한 알고리즘을 설명한다. 

 

[ 알고리즘 설명 ]

 

'1924' 에서 '94'를 만드는 방법은

10의 자리에 들어갈 수 있는 수 중 가장 큰 수를 찾고 일의 자리에 들어가는 수 중 가장 큰 수를 찾는 방법이다.

[ 1 9 2 ] 중에서 가장 큰 수 인 9를 찾고 그 이후 수 인 [ 2 4 ] 에서 가장 큰 수를 찾는다. 

이 방법을 이용할 경우 가장 큰 수 조합을 찾을 수 있고, 이 알고리즘 또한 탐욕법이라고 할 수 있다. 

 

나는 이 방법을 무식하게 이용하여 max함수를 이용하여 무식하게 문제를 풀었는데 

max로 찾기보다는 반복문을 돌려가며 번째에 맞게 찾는 것이 훨씬 빠르게 문제를 풀 수 있다. 

(max로 찾았다 효율성 다 실패하였다. ) 

 

내가 짠 코드는 아니지만 참고하기 좋은 방법의 코드로 설명해본다. 

내가 짠 코드가 아니므로 전체를 가지고 올 수 는 없었으니 

내가 놓친 중요한 부분만 설명한다. 

[ 이 풀이는 알고리즘이 다르다.] (비슷한 자리수를 기반으로 계산하고 있기는 하다.) 

for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)

stack에는 먼저 제일 앞자리 수가 들어가 있다. num에는 이후 값들이 차례대로 들어오게 된다.

예시 문제에 있는  "1231234"를 예로 들어 문제를 푼다. 

먼저 stack에는 [1]이 들어있다. 여기에서 num은 첫번째 for문을 돌면서 2가들어오는데, 

[num = 2, stack = 1, k = 3]

2가 1보다 큼으로 1을 뺴고 2를 넣는다.

여기에서 중요하게 작용하는 것이 k인데, k는 뺄 수 있는 수의 개수가 된다.

1보다 2가 크게 되므로 1 하나를 뺀다. 

[num = 3, stack = [2], k =2 ] 

그럼 stack은 [2]이고 다시 반복문을 돈다. 2와 3을 비교 해서 또 한번 3이 2보다 크므로, stack은 3이 된다. 

똑같이 stack을 뺴고 k를 뺀다. 

[ num = 1, stack = [3] k = 1] 

이제 num으로 더 작은 값이 들어오므로  while 조건에 맞지 않아 다음으로 넘어간다.

[num = 2, stack = [ 3 1 ], k = 1 ] 

다시 stack의 마지막 값보다 큰 값이 들어왔으므로, 앞의 과정을 반복한다. 

[num = 3 , stack = [ 3 2 ] , k = 0 ]

이제 k는 0이 되었다. k가 0이므로 앞의 while조건문에 부합하지 않고. 

[num = 3, stack = [ 3 2 3 ], k = 0 ]

[ num = 4, stack = [ 3 2 3 4 ], k = 0 ]

이 된다. 최종 stack에 담긴 값이 3234로 가장 큰 수를 만들게 된다. 

 

그리고 이후

if k != 0 : 
	stack = stakc[:-k]

가 추가로 들어가야 하는데 이 경우는 다 돌았지만 크기순으로 배열되어 있어, k개를 빼지 못한 경우를 의미한다. 

이럴 경우 순차적으로 k개를 뺴고 입력하면 된다. 

 

 

 

이렇게 쉽고 효율적으로 푸는 방법은 써 봤고 , 앞의 알고리즘을 이용하여 어렵게 푼 나의 풀이를 설명한다. 

자릿수를 이용하여 비교를 한다는 생각에서 착안하였다. 

앞의 코드가 훨씬 간단하고 이해하기 좋으니 그 코드를 이용하도록 하자... 

여기에서 num = [ int(i) for i in number] 가 지워진 이유는 이 과정에서 너무 많은 수가 들어온 경우 

런타임 오류가 생긴다. 이를 위해 maxstr로 숫자만 비교하는 코드를 따로 적용하였다. 

그 코드는 간단하고 귀찮으니 따로 첨부하지 않는다.  그냥 숫자로 된 문자  가장 큰 수 반환해주는 함수이다. 

 

그렇게 문자만 비교해주도록 함수를 수정하니 모두 통과가 되었다.! 

하지만 앞으로는 앞서 말한 알고리즘을 쓰도록 하자.. 훨씬 깔끔하므로...