[Python] 프로그래머스(Programmers): 큰 수 만들기

문제

코딩테스트 연습 - 큰 수 만들기

---

풀이

a. 시간 초과 풀이

범위 내의 index에서 최대 수를 구하는 것을 반복하는 방식으로 문제를 풀이하였다.
만들어야 하는 자리 수는 number의 길이 - k개이고, 가장 높은 자리의 숫자부터 차례로 결정하여 문자열을 얻어내야 한다

1. start_index = 0, size = (숫자의 길이) - (제거해야 할 숫자 k개) - 1 로 설정
2. k개를 제거할 때까지, 삭제 가능한 범위 내에서 최대 수를 구하여 answer 문자열에 추가하기를 반복
3. k개를 제거한 뒤, 선택해야 할 숫자의 갯수를 충족하지 못한 경우, 남은 수를 answer 문자열에 추가

def solution(number, k):
    """
    start_idx: 탐색을 시작할 start index
    count: 제거한 숫자의 갯수
    size: 선택해야 할 숫자의 갯수
    """
    answer = ''
    start_idx, count = 0, 0
    size = len(number) - k - 1      # 선택해야 하는 숫자의 개수

    # k개를 제거할 동안 반복문 수행
    while count < k:
        # 삭제 가능한 범위 내에서 최대의 수를 구함
        # 현재 범위 내에서 택할 수 1개를 제외하고 이후에 추가로 택해야 할 수 size개를 남겨두어야 하므로,
        # 탐색 범위를 [start_idx, len(number)-size)로 설정
        num, new_idx = max([(i, idx) for idx, i in enumerate(number[start_idx:len(number) - size])], key=lambda x: x[0])
        answer += num

        count += new_idx  			# 제거한 숫자의 개수를 카운트
        start_idx += new_idx + 1  	# 최대의 수 + 1을 새로운 start_idx로 설정
        size -= 1

    # k개를 제거한 뒤, 추가해야 할 수가 남은 경우를 처리
    while size >= 0:
        answer += number[start_idx]
        start_idx += 1
        size -= 1

    return answer

접근 자체는 틀리지 않았지만,  8, 10번 케이스에서 계속하여 시간 초과가 발생하였다.

 

b.  최종 풀이

최대 숫자인 '9'를 만났을 때는 반복문을 수행하지 않도록 break문을 걸어주게 수정하였더니 통과

def solution(number, k):
    answer = ''

    size = len(number) - k - 1
    start_idx = 0
    
    while size>=0:
        if number[start_idx] != '9':
            for x in range(start_idx+1, len(number)-size):
                if number[start_idx] < number[x]:
                    start_idx = x
                    if number[x] == '9': break
                        
        answer += number[start_idx]
        start_idx += 1
        size -= 1

    return answer

stack을 사용하여 구현하는 것이 훨씬 깔끔한 코드인 것 같다. nested if 너무 싫다