04 큰 수 만들기 - 탐욕법 (Greedy)

문제 설명

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

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

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

 

제한 조건

number는 1자리 이상, 1,000,000자리 이하인 숫자 입니다.

k는 1이상 number의 자릿수 미만인 자연수입니다.

---

✅ 원칙

앞자리에 큰수가 오는 것이 전체를 크게 만든다 - 큰수부터 골라 담기

- 작은 걸 빼되, 앞에 나온걸 빼야함

- 지금 담으려는 것보다 작은 것들은 도로 뺀다!

- 뺄 수 있는 수효에 도달할 때까지만 (k)

- 큰 수가 앞자리에, 작은 수가 뒷자리에 올 수 있도록

 

number = 4177252841, k = 4

number	answer	k	설명
4177252841	4	0
4177252841	41	0
4177252841	47	1	현재 추가된 7 보다 추가 되어있는 앞의 수 1이 더 작으므로 제거
	7	2	현재 추가된 7 보다 추가 되어있는 앞의 수 4가 더 작으므로 제거
4177252841	77	2
4177252841	772	2
4177252841	7725	2
	775	3	현재 추가된 5 보다 추가 되어있는 앞의 수 2가 더 작으므로 제거
4177252841	7752	3
4177252841	77528		현재 추가된 8 보다 추가 되어있는 앞의 수 2가 더 작으므로 제거
	7758	4	cnt == k (4) 가 됐으므로 Loop 종료
4177252841	775841		나머지 숫자 연결

* 주의
- 이미 정렬되어있는 경우, 뒤에서 k개 만큼 빼야 큰 수가 됨

 

구현

1. 주어진 숫자로부터 하나씩 꺼내서 모으기

2. 모아둔 것 중 지금 등장한 것보다 작은 것들은 빼낸다

3. k를 못채운 경우 - 자릿수 계산

 

> 그리디 : 앞 단계의 선택이 다음 단계의 동작 해의 최적성에 영향을 주지 않음

---

내 풀이

def solution(number, k):        # 문자열형식의 숫자, 제거할 수의 갯수 k
    answer = ''                 # 만들 수 있는 가장 큰 숫자

    numbers = list(map(int, number))
    numbers.sort()              # 오름차순 정렬
    print(numbers)

    for i in range(0, len(number)):
        b = False                               # 제거 여부 체크
        for j in range(0, k):
            if number[i] == str(numbers[j]):     # 작은 수에 해당하면 순서대로 제거
                b = True
                break

        if b == False:
            answer += number[i]



    return answer

 

응 개망했고 못풀었다

 

💯 정답

def solution(number, k):
	answer = ''
    collected = []		# 숫자를 모아서 큰수를 만들기 위한 리스트 (mutable)
    
   	for i, num in enumerate(number):	# 인덱스와 문자 하나씩 탐색
    	while len(collected) > 0 and collected[-1] < num and k > 0:	# 문자열 대소 관계 = 한자리 숫자 대수관계
        	# 현재 숫자가 이미 담아져 있는 숫자보다 클 경우 빼야함, 빼낼 갯수도 남아있어야함
            collected.pop()		
            k -= 1	# k값 감소
            
        if k == 0:
        	collected += list(number[i:])	# i이후의 문자열 다 추가
            break
            
        collected.append(num)	# 현재 문자 추가
        
    collected = collected[:-k] if k > 0 else collected
    
    answer = ''.join(collected)
    
    return answer

- 복잡도 : number에서 한글자 씩 Loop

= O(n)

- 이렇게 간단하게 풀릴 수 있는 문제라니~~~~ 공부해라

 

 

 

어떻게 접근해야하는지 몰랐으니까 꼭 다시 풀어보자