파이썬(알고리즘) :: m개의 숫자를 제거할때, 가장 큰 수 출력 (스택 문제)

이번에는 알고리즘 유형 중 하나인 스택에 대해 정리 해보려고 한다.

 

문제 유형으로는 숫자로 이루어진 문자열에서 m개의 숫자를 제거할때 가장 큰 수를 출력하는 문제를 선택하였다.

 

# 풀이 과정

입력 받은 m개의 숫자 만큼 반복문을 돌리면서 제거할 숫자를 탐색해야 한다.

 

탐색하기 위한 가장 좋은 방법은 아래와 같이 "7' 이라는 숫자를 예를 들어 설명하자면, 7 앞에 있는 4와 2는 7 보다 작은 숫자 이기 때문에 제거할 수 있다. 즉, 연속된 두 인덱스의 숫자를 비교하여 크면 stack에 담고 작으면 pop 시킬 수 있다. 

 

이러한 과정을 m번 만큼 반복한 후 최종 stack을 return 시키면 된다. 

 

 

위 과정대로 m번 만큼 반복이 되어서 깔끔하게 정답이 나올 수 있지만, 예외적으로 리스트의 길이 만큼 탐색을 하였지만, m번 만큼 pop 시키지 못할 수 도 있다,

 

이런 예외 사항을 고려하며 위 과정을 마친 후, 반복하지 못한 -m번 인덱스 만큼 stack에서 잘라주면 된다. 

 

 

# 풀이

def check(num, m):
    num = list(map(int, str(num)))
    stack = []

    for i in num:
        while stack and m > 0 and stack[-1] < i:
                stack.pop()
                m -= 1
        stack.append(i)
            
    if m!=0:
        stack=stack[:-m]
    
    result = ''.join(map(str, stack))

    return result

input1 = "4275923"
input2 = "98537654312"

m1 = 3
m2 = 5

print(check(input1, m1))
print(check(input2, m2))

 

# 실행 결과

7923
987654