1. 개념 정리

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 입출력 예시

number / k / return
"1924" / 2 / "94"
"1231234" / 3 / "3234"
"4177252841" / 4 / "775841"

3. 풀이 과정

접근의 방식에서 여러 방향을 건드려보다 보니, 생각보다 간단한 문제인데도 시간이 오래 걸린 문제였답니다!😭

저의 처음 의사코드는 대략 이런 방식이였어요

리스트의 원소요소 개수만큼 반복을 하되, 각 요소가 자신의 뒤에 있는 요소와 크기비교 연산을 함
-> 만약 뒤에 있는 친구가 더 크면, 가르키고 있는 친구를 지워야 하고, k 감소 해야함
-> 참조 중인 리스트를 바로 변경할 수 없으므로 (len Error), append 하지 않고 k를 감소시킴
-> 만약 뒤에 숫자가 더 큰게 아니라면 가르키고 있는 대상을 append함
이 연산의 끝에 k가 남았다면, 리스트의 뒤 원소를 k개 만큼 소거

그러나, 바라보고 있는 i 번째의 요소와, 뒤에 있는 i + 1 번째의 단순비교로는 알아낼 수 없는 여러 케이스들이 있었답니다. 예시의 3번 경우처럼 "4177252841"이 "775841" 로 치환되는 것처럼, 두개 이상의 숫자가 지워지는 경우도 있었어요.

흠..

계획 변경입니다..

다음으로 생각한 것이 완전탐색!

def wantam(k, num):
    if k == 0:
        global answer
        answer.append(num)
        return
    length = len(num)
    for i in range(length):
        tmp = list(num)
        tmp.remove(num[i])
        wantam(k - 1, ''.join(tmp))

def solution(number, k):
    global answer
    answer = []
    
    wantam(k, number)
    
    return(max(answer))

가볍게 생각해서, 모든 경우를 돌면서 조합을 찾아 max값을 뽑아내면 된다 생각했지만!

물론 이것은 시간 초과였지요..!

종국적인 해결방식은 stack을 이용한 풀이방식이였답니다.

def solution(number, k):
    answer = []
    
    for i in number:
        while answer and k > 0 and answer[-1] < i:
            answer.pop()
            k -= 1
        answer.append(i)

    if k > 0:
        answer = answer[:-k]
    
    return(''.join(answer))

특정 숫자를 스택에 더할 때, 지금 스택에 남아있는 숫자들이 만약 더해질 숫자보다 더 작다면,
반복하여 스택을 pop하는 방식이랄까요!

마지막에 k 가 잔존하면 처리되는 과정을 조금 헷갈리긴 했지만! 일단 해결!

기회를 보아 좀 더 자세히 정리하겠습니다!