그리디 알고리즘의 두 번째 문제이다. 프로그래머스 레벨 2 문제였고, 단순 구현을 넘어 최대한 효율적으로 짜는 것이 관건이었다.
문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다.
해결 아이디어
위 문제는 주어진 숫자 문자열에서 k개의 숫자를 제거해 가장 큰 수를 만드는 문제이다. 이때 앞자리부터 가장 큰 숫자를 선택하는 그리디 전략을 사용하여 최적의 해를 구한다.
내가 스스로 생각한 방법은 다음과 같았다.
1. 현재 자리에서 선택할 수 있는 범위를 정한다.
이전 단계에서 선택한 숫자 인덱스의 다음 자리부터, 남은 숫자를 다 채우기 위해 필요한 최소 숫자만큼의 범위까지만 탐색한다.
2. 그 범위에서 가장 큰 숫자를 선택하고, answer에 추가한다.
3. 선택한 숫자의 인덱스 다음 자리부터 다시 1~2번을 반복한다.
4. 모든 숫자를 선택할 때까지 이 과정을 반복하면 최종적으로 가장 큰 수가 만들어진다.
그래서 나는 아래와 같이 코드를 작성하였다.
def solution(number, k):
answer = ''
max_index = -1
cnt = len(number)-k
while cnt > 0:
max = -1
for i in range (max_index+1,len(number) - cnt + 1):
if max < int(number[i]):
max = int(number[i])
max_index = i
cnt -= 1
answer += number[max_index]
return answer
max_index랑 max의 초기값을 0으로 두었더니 오류가 생겨 -1로 두었다. (number에 0이 들어갈 수 있기에 아예 들어가지 않는 -1로 하는게 좋은 것 같다.)
또한 for문에서 i의 범위가 조금 헷갈렸는데, max_index의 다음원소부터, 전체 길이에서 골라야되는 남은 원소가 모두 끝에 몰려있는 경우의 가장 인덱스 위치까지로 잡았다.
그렇게 선택이 모두 완료될 때까지 매 순간 선택된 최댓값을 answer에 이어붙여 정답을 반환하도록 했다.
그러나, 이 문제는 테스트 케이스 2가지를 통과하지 못하였다.
시간복잡도가 최악인 경우 O(n^2)이기에, 해당 케이스에서는 시간 초과로 실패하였다.
분기한정법?
테스트 케이스 중 이런 경우가 있을 수 있다.
1999999999.....
위에 내가 적은 로직은, i의 범위안에서 계속 순회하면서 최댓값을 찾는데, 사실 모든 자리의 숫자는 9보다 클 수는 없기 때문에, 9가 나오는 순간 최댓값은 9로 확정이된다. 즉, 9가 나오면 반복문은 종료된다는 것이다.
따라서 코드를 아래와 같이 수정하였다.
해결코드 <Python>
def solution(number, k):
answer = ''
max_index = -1
cnt = len(number)-k
while cnt > 0:
max = -1
for i in range (max_index+1,len(number) - cnt + 1):
if max < int(number[i]):
max = int(number[i])
max_index = i
#9가 나오면 반복문 종료
if max == 9:
break
cnt -= 1
answer += number[max_index]
return answer
위와 같이 수정하였더니 모든 테스트 케이스를 통과하였다.
그러나 여전히 시간복잡도는 O(N^2)이다.
따라서 다른 분들의 코드를 보았는데, 스택을 사용하여 시간복잡도를 O(N)으로 획기적으로 줄일 수 있었다.
스택을 이용한 풀이?
def solution(number, k):
stack = [number[0]]
for num in number[1:]: #두 번째 숫자부터 순회
while len(stack) > 0 and stack[-1] < num and k > 0:
k -= 1 #pop으로 없앤 애는 어차피 작은 숫자라 쓰일 일 없음: 제거하는 숫자.
stack.pop() #stack의 top보다 num이 더 크면 stack.pop()으로 현재 top 없앰
stack.append(num) # 더 크다면 stack에 넣음.
if k != 0:
stack = stack[:-k] # 제거 횟수를 다 사용하지 않았다면 뒷 부분 자르기
return ''.join(stack)
스택은 LIFO(Last-In-First-Out)구조로, 항상 가장 마지막 숫자와 현재 숫자를 비교하기에 적합하다.
현재 숫자가 더 크면, 앞에 있던 숫자를 제거(pop)하면 돼서, 큰 수를 남기고 불필요한 숫자를 제거해 큰 수를 만드는 데 최적화된 자료구조다.
stack에서의 push/pop은 시간복잡도가 O(N)으로 효율적이다.
숫자를 보며 앞의 숫자가 작으면 제거
제거할 기회를 다 쓰면, 그냥 스택에 쌓음
마지막에 남은 k만큼 뒤에서 제거
한 번의 순회로 끝나므로 O(N)
예를들어, number = "54321"이고 k=2이면 while에서 pop을 하지 못하고 스택 뒤에서 k개를 제거하는 것이다.
['5,'4','3','2','1'] -> ['5','4','3']
해결 코드 <JavaScript>
function solution(number, k) {
let answer = '';
const stack = [];
for (let i = 0; i < number.length; i++) {
const num = number[i];
while (stack.length > 0 && stack[stack.length - 1] < num && k > 0) {
stack.pop();
k--;
}
stack.push(num);
}
if (k > 0) {
stack.splice(stack.length - k, k); //배열에서 원하는 인덱스부터 k개를 제거하는 메서드
}
answer = stack.join('');
return answer;
}
해당 코드를 자바스크립트로 바꾸면 다음과 같다.
python에서는 append()를 사용하지만, JS, Java,C++ 등 다른 언어는 push()를 사용한다.
