알고리즘 유형 : 그리디
풀이 참고 없이 스스로 풀었나요? : X
https://programmers.co.kr/learn/courses/30/lessons/42883?language=python3
소스 코드(파이썬)
def solution(number, k):
answer = ''
# 원본 변조를 피하기 위해 다른 변수에 카피해서 조작
k_copy = k
# 최종적으로 결과 값을 담아낼 스택
bigger = []
for num in number:
num = int(num)
# 스택에 숫자가 존재하고, 제거 횟수가 남아있고, 스택의 마지막 숫자가 현재 순회 숫자보다 작은 동안 계속 스택을 pop하고 제거 횟수를 1 감소시킨다.
while len(bigger) > 0 and k_copy > 0 and bigger[-1] < num:
bigger.pop()
k_copy -= 1
# while이 끝나고 현재 순회 숫자를 스택에 추가한다.
# 두 구문의 의미를 요약하면, 우선 number의 모든 숫자를 for로 순회한다. 각 숫자에 대해, 스택의 마지막 숫자부터 비교해서 자신보다 작은 것들을 모두 pop하여 제거하고 자신을 스택에 추가한다. 이 과정 자체가 그리디이다.
# 각 순회 단계의 숫자에 대해, 지금까지 쌓아 만든 숫자 스택에 대해, 자신이 특정 자릿수의 숫자를 대신해서 들어가려면, 원본 숫자들의 배치 순서를 그대로 지켜야하므로 원래 있던 숫자를 제거하고 자신이 들어가야만 한다.
bigger.append(num)
# number = 97865, k = 1인 경우를 생각해보자.
# 그럼 stack에는 9865가 들어가있고 k는 1이 남아있다.
# 이렇듯, 마지막 즈음에서 비교하려는 숫자 쌍이 내림차순으로 이미 잘 배치되어있다면 원래 있던 숫자를 제거하지 않고 자신을 스택에 추가하게 된다.
# 이런 경우, 뒤에서 k만큼의 숫자를 그냥 빼버리고 출력해주면 된다. 뒤에서 k만큼의 숫자들이 while 로직에 따라 내림차순으로 되어있기 때문에 그대로 빼줘버리면 되는 것이다.
if k_copy != 0:
bigger = bigger[:-k_copy]
answer = "".join(map(str, bigger))
return answer풀이 요약
- 스택을 사용하는 그리디 풀이이다.
-
number의 모든 숫자를 왼쪽부터 순회한다.
순회중인 각 숫자 num에 대해, 스택의 제일 뒤에 있는 숫자부터 비교해나가면서, 만약 제거 횟수가 아직 남아있고 num이 스택의 마지막 숫자보다 크다면, 스택 마지막 숫자를 제거하고 num을 그 자리에 넣어버린다. 물론, 이런 경우가 안 나올때까지 while문 돌면서 쭈욱 제거해주고, 그런 다음 마지막에 num을 스택에 넣어줘야된다.
이 것이 그리디 개념이 적용된 부분인데, 큰 숫자를 구하기 위해서는 보통 가장 높은 자릿수에 가장 큰 숫자를 넣는게 일반적이다. 그러므로, 이미 구하고 있는 가장 큰 숫자인 "스택"에, num을 스택 마지막 숫자부터 비교해나가면서, 자신이 올라갈 수 있는 최대한의 자릿수까지 비집고 올라가 자리잡는 로직인 것이다.
-
이 때 주의할 점이, number = 97865, k = 1인 경우에는 for를 다 돌고나면 stack에는 9865, k = 1이 된다. 아직 제거 횟수가 남아있다.
이 경우는, 이미 어느정도 내림차순으로 배치되어있는 부분들이 어느 정도 많게 되면, 그러한 각 경우에는 제거를 수행하지 않고 바로 스택의 마지막 자리에 num을 추가하게 되므로, 끝까지 순회하고도 k가 남을 수도 있다.
이 때, stack의 마지막부터 k개의 숫자는 반드시 내림차순으로 배치되어있다.(while 로직에 따라)
그러므로, 현재 stack에 있는 9865에서 마지막에서부터 k(=1)개를 지워준 986이, 9865에서 k를 다 소진하고 만들 수 있는 가장 큰 수이다.
배운 점, 어려웠던 점
- 아직까지 그리디 문제라고 하면, 단순히 for와 if의 활용에서 사고가 벗어나질 못하는 것 같다. 이런 식으로 스택을 활용하기도 하고 여러 기술을 활용하는 그리디 유형을 많이 풀어봐야겠다.
- 그리디 아이디어를 생각해내는게 너무 어려웠다. 결국 다른 사람 풀이를 참고해서 풀었다.
