❓프로그래머스 : 큰 수 만들기
〽️ 문제 요약
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하면 되는 문제
🤔 접근법
그리디 문제라는 것을 알고 문제를 풀이했음에도 마땅히 풀이가 떠오르지 않아 고생했던 문제이다.
처음에는 그리디하게 힙을 활용해 앞에서 부터 가장 작은 값을 k번 제거하는 방법을 시도했다. 꽤 일리있어 보이는 방법이었지만 예시 케이스 3번 같이 “4177252841” 수에 대해서 가장 작은 수를 순서대로 4번 제거하는 경우 “477584”가 되어 오답을 출력하게 된다. 이와 같이 작은 수가 뒤에 몰려있을 경우 앞에 제거해야 하는 ‘조금 더 큰’ 작은 수가 제거되지 않는다.
두 번째 방법으로는 완전 탐색으로 접근해보았다. itertools 모듈의 combinations를 활용해 len(number)개의 수 중 순서대로 len(number)-k개를 뽑는 모든 조합을 구해 최대값을 출력하도록 했다. 예시 케이스들에 대해서 정답은 맞지만 제출했을 때 시간초과를 피할 수는 없었다.
결국 레퍼런스를 참고해 해답을 얻었고, 접근 방법은 스택을 활용하는 것이다.
중요한 점은 앞 단의 숫자가 높은 숫자가 나와야한다는 점이다. 맨 앞에 높은 숫자가 나오는 것이 뒤에 어떤 숫자가 나오던 가장 큰 수가 되기 때문이다. 이러한 측면에서 그리디 문제인 것 같다.
이를 구현하기 위해 스택을 활용해야 한다. 스택에는 최종적으로 결과를 만들 수들을 push하는데, 스택의 가장 뒤 값이 push할 값보다 작다면, 그 이상의 값이 나올 때 까지 수들을 제거하는 것이다. 이 때 최대 k번 수를 제거할 수 있으며, 앞자리에 k번 제거할 때 만들 수 있는 수중 가장 높은 수들을 배치할 수 있으므로 가장 큰 값을 만들어낼 수 있다.
이 경우 예외 케이스로 number 문자열에 [4, 3, 2, 1]이 주어진다면 매번 push하는 값이 이전의 push된 값보다 작아서 제거되는 경우가 없으므로 모두 삽입되게 된다. k개의 수가 제거되지 않은 채 모든 수가 stack에 push되는 경우 남아있는 k 만큼 stack에서 잘라서 수를 가져와야 한다.
🔡 코드
def solution(number, k):
stack = []
for num in number:
while stack and k and stack[-1] < num:
stack.pop()
k -= 1
stack.append(num)
return ''.join(stack[:len(stack)-k])📚 고찰
여러개의 수가 나열되어있을 때 n개를 제거해서 가장 큰 수를 만들어야 하는 경우 혹은 가장 작은 수를 만들어야 하는 경우를 활용해야 하는 문제에 위와 같이 스택을 활용해서 접근해보자. 실용적인 테크닉인 것 같다.
그리고 실전에서 시간이 충분히 있다면 예외 케이스에 대해서 충분히 스스로 고려해보고 제출하는 습관을 가져야 할 것 같다.
