[탐욕법] 큰 수 만들기 - Level 2

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

 

문제 설명

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

 

 

---

✔ Solution

def solution(number, k):
    num_array = []  # 숫자를 모아서 큰 수를 만들 때 쓰일 배열

    # k개 만큼의 숫자를 빼냈을 때, i의 인덱스를 기억하기 위해서 i를 사용
    for i, num in enumerate(number):
        while len(num_array) > 0 and num_array[-1] < num and k > 0:
            num_array.pop()  # 리스트이 맨 끝에 있는 원소 하나를 없앤다.
            k -= 1


        #  더이상 뺄게 없으면 남은 거 전부 추가
        if k == 0:
            num_array += list(number[i:])
            break

        num_array.append(num)
     # 만약 빼지 못했으면 삭제 아니면 그대로
    num_array = num_array[:-k] if k > 0 else num_array

    answer = ''.join(num_array)
    return answer

 

⭐ 문제 포인트

 

앞에서부터 수들을 탐색하여 만약 탐색했던 수 보다 큰 수가 나올 경우 이전에 탐색된 수들을 제거

 

1. 이전에 탐색했던 수들을 array에 저장
2. 현재 탐색 중인 수와 array에 저장되어 있는 수들을 비교
   -  만약 스택에 저장된 수가 더 작을 시 제거, 동시에 k를 1씩 감소
   -  더 이상 제거할 수가 없을 때 현재 탐색 중인 수를 저장
3. k가 0이 될 경우 array에 저장된 수 + 탐색할 남은 수들이 가장 큰 수
4. k가 0이 아닌 상태로 탐색이 끝날 경우 array에 저장된 수의 뒤에서부터 k개 만큼 제거하면 가장 큰 수
5.  join() 함수를 통해 가장 큰 수로 기록된 array을 문자열로 변경

 

✔ Solution 2 - 다른 사람 답

def solution(number, k):
    stack = []
    for i in range(len(number)):
        while stack and k>0 and stack[-1]<number[i]:
            stack.pop()
            k-=1
        stack.append(number[i])
    return ''.join(stack[:len(number)-k])