프로그래머스(탐욕법, Greedy)-큰 수 만들기-Python

문제 설명

어떤 숫자에서 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

 

---

내 문제풀이

1. 완성된 수를 넣을 리스트(new_list)에 number의 첫 원소 수를 넣는다.

2. number의 길이만큼 도는 반복문 내부에서 while문을 수행한다. k, new_list가 존재하고 new_list의 가장 마지막 원소가 number의 현재 원소 값보다 작은 경우에 수행한다. 이 경우에 new_list의 마지막 원소를 제거하고, k-1을 해준다. 

3. while문이 끝나면 number의 현재 원소 값을 new_list에 추가한다.

4. 내가 생각한 반환하는 경우의 수는 총 3가지이다. 

4-1. 만약 for문이 다 끝나기 전, k가 0이 되었을 때 현재 number 원소의 인덱스 값을 answer에 저장하고 반복문을 나온다.이 경우는 뺄 수 있는 만큼의 수를 이미 다 뺸 것이기 때문에 number에 남은 뒤의 숫자들을 new_list에 추가해주고 new_list를 반환한다.

4-2. 만약 위의 while문에서 계속 new_list의 가장 마지막 원소가 number의 현재 원소 값보다 큰 경우, while문이 실행되지 않고 new_list에 number의 원소만 append할 수 있다. 따라서 for문이 다 끝났지만 k가 0이 아닌 경우, new_list의 원소는 이미 가장 큰 수의 조건은 만족하고 있으므로 [:-k]의 인덱스 슬라이싱을 사용한다. 따라서 남은 k만큼의 뒷 부분 숫자를 잘라서 반환한다.

4-3. 위의 for문에서 k가 0이 되었지만 그 전에 for문이 끝난 경우, new_list가 깔끔하게 완성된 것이다. 따라서 그대로 new_list를 반환한다.

 

내 코드 - 파이썬

def solution(number, k):
    answer = 0
    new_list = [number[0]]
        
    for n in range(1, len(number)):
        if k == 0:
            answer = n
            break
        
        while k and new_list and new_list[-1] < number[n]:
            new_list.pop()
            k-=1
        new_list.append(number[n])
            
    # 위의 while문에서 new_list[-1]보다 작은 수만 들어와서 계속 append 하고 k가 남은 상황
    if k!=0:
        return ''.join(new_list[:-k])
    
    # 위의 for문을 다 돌고 나온 상황(k==0 조건문에 걸리기 전에) -> 깔끔하게 new_list 완성
    if answer == 0:
        return ''.join(new_list)
    
    # 위의 for문을 다 돌기 전 k==0에 걸린 상황
    new_list.append(number[answer::])     
    return ''.join(new_list)