[프로그래머스] 큰 수 만들기 - 그리디 greedy | 스택 Stack (python) (1)

1. 문제 설명

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

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

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

 

---

2. 제한 조건

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

---

3. 입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

---

4. 나의 풀이

이번 문제는 탐욕법을 이용하여 푸는 문제이다. 주어진 숫자에서 k의 갯수만큼 빼서 가장 큰 숫자를 만들어야 한다. 처음에는 문제를 보고 조합을 이용해서 풀어야 하나 한참을 고민했다. 그러나 제한 조건의 number의 범위가 커서 그 생각을 접었다. 탐욕법을 어떻게 써야할지 고민을 많이 했는데, 우선 생각나는대로 문제를 먼저 풀어보기로 했다.

k가 주어졌기 때문에 return 해야할 숫자의 길이는 정해진 상태이다. 따라서 앞에서부터 정답에 넣을 숫자를 골라보기로 했다.

마지막 테스트 케이스를 예시로 들어보았다. 이 경우 k가 4이기 때문에 최종 숫자는 6자리가 되고, 만약 뒤의 다섯자리가 답에 들어간다고 치면 앞에 있는 다섯자리 중 한 숫자는 무조건 답에 들어가야한다. 따라서 앞의 숫자 중 가장 큰 숫자를 골라 답에 추가해준다.

첫번째 숫자를 고르면, 그 앞에 있는 숫자들은 이제 쓸모가 없으니 고려하지 않는다. 6자리의 숫자중 한자리가 결정되었으니 이제 나머지 다섯자리를 생각해줄 차례이다. 마찬가지로 뒤의 네자리가 답에 들어간다고 치면 앞에 있는 숫자중 한 숫자는 무조건 답에 들어가야한다. 따라서 지운 숫자와 이미 결정된 숫자를 제외한 4번째 7부터 가장 큰 숫자를 골라준다.

뒤에도 똑같이 진행한다.

마지막 max 숫자인 8을 고르고 나니, 정해진 4개의 숫자 (7758)을 제외하고 남은 정답자리와 리스트의 남은 숫자의 갯수가 일치했다. 이 남은 숫자들은 정답에 골라서 추가해주면 정답이 된다. (775841)

 

def solution(number, k):
    answer = ''
    num = list(number) #문자열을 리스트로 쪼개는 과정
    
    i = len(num) - k - 1
    while(True):
        if num[:-i] == []:
            answer += max(num)
            break
        answer += max(num[:-i])
        del num[:num.index(max(num[:-i])) + 1]
        i -= 1

    return answer

 

코드를 완성하고 제출하니 두가지 경우에서 시간초과가 떠버렸다. ᆓᗣᆓ,,,,,,,,,,, 테스트 8 또한 5311ms,,,,,,,,,

아마 알고리즘 자체에서 효율성 문제가 나는 것 같았다. 반복문 안에서 리스트를 쪼개고 max까지 써버렸으니 말이다. 질문하기도 찾아보고 주피터로 온갖 테스트케이스를 해보았지만 모두 잘 돌아갈 뿐이었다..ㅠㅅㅠ 고치고 싶었지만 이미 저 풀이를 하는데에도 시간이 많이 소요되었기 때문에 다른 풀이들을 찾아보았다. 그 결과 다른 방법으로 푼 해설을 발견했다. 무려 스택을 써서 푸는 방법이었다.

다음 포스팅에서 다루어 보도록 하겠다.