[프로그래머스] 탐욕법(Greedy) - 큰 수 만들기 (Level 2)

큰 수 만들기

---

풀이과정

1. number에서 k개의 수를 제거하므로 만들 숫자는 len(number)-k자리이다.
2. number에서 큰 수들을 차례로 골라 answer에 추가하는데, 이 때 해당 수 뒤에 최소 len(number)-k-1개의 숫자가 남아있어야 len(number)-k자리 숫자를 완성할 수 있다. 그러므로 number[0]부터 number[k]까지의 숫자 중 최댓값을 찾아 answer에 추가한다.
3. answer에 하나의 숫자를 추가한 후에는, 추가한 숫자의 뒤부터 len(number)-k자리 수를 완성할 수 있는 위치의 숫자까지의 최댓값을 찾아 answer에 추가한다.
4. 이 과정을 len(number)-k번 반복한다.

Python Code

def solution(number, k):
    answer = []
    number = list(map(int,number))
    start = 0
    n = k+1
    for i in range(len(number) - k):
        answer.append(0)
        for j in range(start, n):
            if number[j] == 9:
                answer[-1] = number[j]
                temp = j
                break	#9인 경우에는 반드시 최댓값이므로 for문을 빠져나감
            if answer[-1]<number[j]:
                answer[-1] = number[j]
                temp = j
        start = temp+1
        n += 1
        
    return ''.join(list(map(str,answer)))

오류와 해결

처음에 max 함수를 사용해서 코드를 짰더니 맞긴 했지만 시간초과가 발생했다. max 함수를 쓰면 테스트 10을 통과할 수 없다고 한다. 그래서 max 함수를 쓰지 않고 answer에 일단 숫자를 추가한 후 뒤에 더 큰 숫자가 있으면 그 숫자로 바꾸는 방법으로 코드를 짰다. 그런데 이 방법으로도 테스트 10에서 시간초과가 발생했다. 숫자가 9인 경우에는 더 최댓값을 찾지 않도록 break를 걸었더니 그제서야 테스트 10을 통과할 수 있었다. number에 9가 많은 케이스에서는 이 방법이 빠르지만 다른 케이스에서는 max 함수를 쓴 방법이 빠를 때도 있는 것 같다.

def solution(number, k):
    answer = ''
    number = list(map(int,number))
    start = 0
    n = k+1
    for i in range(len(number) - k):
        temp = number[start:n]
        index = temp.index(max(temp))
        answer += str(temp[index])
        start += index + 1
        n += 1
        
    return answer