[문제 풀이] 큰 수 만들기 - Greedy

요구 사항

문제 풀이

import java.util.Arrays;

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        
        char[] numberArray = number.toCharArray();
        int numberSize = numberArray.length;
        int limit = numberSize - k;
        int[] stack = new int[numberSize];
        int stackIdx = 0;
        
        for (int i = 0; i < numberSize; i++) {
            int n = Character.getNumericValue(numberArray[i]);
            while (0 < i && 0 < stackIdx && stack[stackIdx - 1] < n && k > 0) {
                stackIdx--;
                k--;
            }
            stack[stackIdx] = n;
            stackIdx++;
        }
        
        for (int i = 0; i < limit; i++) {
            answer.append(stack[i]);
        }
        return answer.toString();
    }
}

• number값으로 들어오는 4177252841값을 array형태로 변형 시킨다.
• number에서 k개 만큼 제거한 수의 limit을 지정한다.
• 빈 int형 number 배열의 크기만큼의 array Stack을 선언한다. [0,0,0,0,0,0,0,0,0,0]
• i가 0번째 일때는 4값을 stack에 쌓아준다. [4,0,0,0,0,0,0,0,0,0]
• i가 1번재 부터는 while 루프를 돌려서 현재 선택된 값에 이전값들과 계속 비교해 준다.
• 만약 현재 선택된 값이 Stack에 쌓아두었던 이전값과 비교했을때 더 작다면 해당 인덱스에 덮어씌운다.
• 반대로 이전값이 더 크다면 stackIdx에 1을 더해 다음 칸에 값을 넣어주도록 한다.
• 그리고 값이 하나씩 지워질때마다 k의 값에 -1을 해주면서 더이상 지울 값이 없을때 까지 반복해준다.
• 1은 4보다 작으므로 [4,1,0,0,0,0,0,0,0,0] 쌓이게 되고
• 그다음 7은 1보다 크므로 [4,7,0,0,0,0,0,0,0,0] 되고 루프를 돌아서 그 앞에 4와 비교했을 때도 더 크기 때문에 [7,0,0,0,0,0,0,0,0,0] 이된다. 이때 k는 4에서 두개의 값이 삭제 됬으므로 2가 된다.
• 그다음 7은 [7,0,0,0,0,0,0,0,0,0] stack의 이전값보다 크지 않기 때문에 [7,7,0,0,0,0,0,0,0,0] 추가된다
• 그다음 2도 똑같이 추가된다. [7,7,2,0,0,0,0,0,0,0]
• 그다음 5는 앞자리 2보다 크기 때문에 [7,7,5,0,0,0,0,0,0,0] 처리되고 k값은 2 -> 1이된다.
• 그다음 2는 그대로 추가가 된다. [7,7,5,2,0,0,0,0,0,0]
• 그다음 8은 앞자리 2 보다 크기 때문에 [7,7,5,8,0,0,0,0,0,0] 처리되고 k 값은 1 -> 0 이된다.
• 이 후에는 더이상 삭제가 불가 하므로 나머지 값을 뒤에 추가해주면 된다.
• 최종 값은 [7,7,5,8,4,1,0,0,0,0] 이 된다.
• 마지막으로 문자열 answer에 limit(6)만큼의 값을 추가해주고 출력을 해주면 "775841"이 출력되는 것을 알수있다.;