문제
풀이
이 문제에 Greedy 알고리즘을 적용할 수 있는 이유는 왼쪽부터 차례로, 그러니까 높은 자리 수부터 차례로 큰 숫자를 채워나가기 때문이다. 맨 앞자리부터 큰 수를 채우는 게 최댓값을 구한 결과를 보장하고, 하나의 수를 채우는 게 다른 자리의 수에 영향을 주지 않아서 적용이 가능한 것이다.
targetLength만큼 반복하며 범위 내의 최댓값을 찾아 결과 String에 append한다.
a. 범위는 이전maxNumberIndex다음부터i + k까지다.number의 맨 뒤에서부터k번째까지는 남겨 놓고- 숫자 하나를 append 할 때마다 한 칸씩 탐색 범위를 뒤로 옮기는 것이다.
b.findMaxNumIndex(): 주어진 범위에서 최댓값을 찾고 그 index를 리턴한다.
Stack을 사용해서 풀면 훨씬 간단하던데, 인덱스로 푸는 연습을 해야 하니까 이렇게 풀고 확실히 이해를 해보았다.
코드
class Solution {
public String solution(String number, int k) {
StringBuilder result = new StringBuilder();
int targetLength = number.length() - k;
int startIndex = 0, endIndex, maxNumberIndex;
for (int i = 0; i < targetLength; i++) {
endIndex = i + k;
maxNumberIndex = findMaxNumIndex(number, startIndex, endIndex);
result.append(number.charAt(maxNumberIndex) - '0');
startIndex = maxNumberIndex + 1;
}
return result.toString();
}
private int findMaxNumIndex(String number, int startIndex, int endIndex) {
int maxNum = Integer.MIN_VALUE;
int maxNumIndex = startIndex;
for (int i = startIndex; i <= endIndex; i++) {
if (number.charAt(i) > maxNum) {
maxNum = number.charAt(i);
maxNumIndex = i;
}
}
return maxNumIndex;
}
}