[python] 탐욕법_큰 수 만들기(2단계)

1.1 탐욕법 (Greedy Algorithm)

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있으면 매우 효과적이고 직관적인 알고리즘이지만, 대부분의 문제에 대해서는 "최적의 해"를 찾을 수 없는 가능성이 크기 때문에 주의해서 사용해야 하는 알고리즘입니다. 매 순간의 선택은 그 순간에 대해서는 최적이었을지라도 그것이 결론적으로 최적이 아닐 수 있기 때문입니다. 그렇기 때문에 그리디 알고리즘을 이용해 문제를 해법을 찾을 경우, 그 해법이 정당한지에 대해서 반드시 확인해 보아야 합니다.

대표적으로 거스름돈 문제가 있으며 다익스트라 알고리즘 또한 그리디 알고리즘이라고 할 수 있습니다.

2. 문제 설명

2.1 큰 수 만들기

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

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

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

2.2 제한 조건

number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.

2.3 입출력 예시

3. 풀이 과정

Stack(LIFO) 활용

Stack을 활용해서 문제를 풀 수 있다는 것을 알게 되니까 push와 pop 두 가지를 사용해서 풀이하는 방식을 생각

핵심은 스택의 마지막 값이 push 할 값보다 작다면 크거나 같은 값이 나올 때까지 값들에 대해서 pop을 하는 것
이렇게 풀이하면 O(n)의 시간 복잡도로 문제 해결 가능

def solution(number, k):
stack = []

for i in number:
	while stack and i > stack[-1]:
    	if k > 0:
        	stack.pop()
            k -= 1
        else:
        	break
    
    stack.sppend(i)

if k > 0:
	for i in range(k):
    	stack.pop()

정답 알고리즘 연습

스택생성 stack = []
number를 순회 for i in number:

알고리즘

스택 생성 => 파이썬에서는 리스트 활용 가능
number를 순회 => for num in number:
다음 조건문을 모두 만족할 경우 명령문을 반복
조건문
1. k > 0
2. 스택이 비어있지 않음
3. 스택 마지막 값 < num
명령문
1. 스택을 pop
k--
스택에 num을 push
k > 0 이상이면 스택에서 k개 삭제 후 join해서 결과 값 반환

def solution(number, k):
    answer = [] # Stack
        
    for num in number:
        if not answer:
            answer.append(num)
            continue
        if k > 0:
            while answer[-1] < num:
                answer.pop()
                k -= 1
                if not answer or k <= 0:
                    break
        answer.append(num)
        
    answer = answer[:-k] if k > 0 else answer
    return ''.join(answer)

다른 풀이, 가장 공감 많았던 풀이

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