최근에 푼 두 문제의 아이디어가 유사해서 뽑아왔다. (둘 다 아이디어 일부 참고함)
몰랐는데 생각보다 스택으로 풀자고 바로 떠올리기 어렵다.. 더 많이 풀어보고 익숙해져야 할 듯 !
문제1) 뒤에 있는 큰 수 찾기
https://school.programmers.co.kr/learn/courses/30/lessons/154539
접근 방식
위치상 가장 근접한 큰 수를 구해야 한다. 입력값의 범위를 보면 순차탐색 방식으로 처리할 수 없다는 점을 알 수 있다. 처음 봤을 때 DP, 그리디, heap 등등 다채롭게 떠올랐는데 스택으로 풀 수 있다는 사실이 새삼 충격스러웠던..
stack의 top과 numbers를 비교해가며 이어지는 가장 큰 수를 구한다. 이때 stack에는 해당 수와 인덱스를 함께 저장해서 해당 인덱스에 대한 뒷큰수를 갱신할 수 있도록 한다.
코드
def solution(numbers):
stack = []
ans = [-1] * len(numbers)
for idx in range(len(numbers)):
while stack and stack[-1][0] < numbers[idx]:
_, _idx = stack.pop()
ans[_idx] = numbers[idx]
stack.append((numbers[idx], idx))
return ans문제2) 큰 수 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/42883
접근 방식
그리디가 가미된 스택 방식의 풀이다.
가장 큰 수를 만들기 위해선 앞자리에는 되도록 큰 수가 와야 한다. (=그리디)
목표는 스택에 가장 큰 수만 남기고 number에서 k개의 수를 제거하는 것이다. 이를 위해선 number의 수와 stack의 top을 비교해서 더 큰 수가 스택에 붙을 수 있도록 해야한다. 이때, k가 0이 된 경우 다 제거했으므로 남은 수를 다 덧붙여도 된다.
테케 12번을 통과하기 위해서는 아직 k개를 제거하지 못한 경우를 떠올려야 한다.
예를 들어, number = [5, 4, 3, 2, 1], k = 2인 경우엔 stack에 계속 숫자가 덧붙여져 [5, 4, 3, 2, 1]이 있을 것이다. 이땐 stack에 앞에서부터 가장 큰 수가 담겨져 있다는 건 보장되기에 뒤에서부터 k개를 제거하면 된다.
코드
def solution(number, k):
number = list(map(int, list(number)))
stack = []
for i in range(len(number)):
while stack and stack[-1] < number[i] and k > 0:
stack.pop()
k -= 1
if k == 0:
stack += number[i:]
break
stack.append(number[i])
if k > 0:
stack = stack[:-k]
return ''.join(list(map(str, stack)))공통점 ?
여기서 두 문제의 공통점은 뭘까?
바로 stack에 담기는 내용이다. 디버깅 해보면 위치에 상대적인 가장 큰 수가 담긴다는 걸 알 수 있다. 앞에서부터 가장 큰 수를 담게 되는 것이다.
두번째 문제를 풀면서 스택을 그리디하게 활용할 수 있다는 점을 알 수 있었다.
