[JAVA] Lv.2 큰 수 만들기 - 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

---

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder(number);
        int idx = 0, cnt = k;
        while (true){
            if(cnt == 0 || idx >= answer.length()-1) break;
            if(answer.charAt(idx) < answer.charAt(idx+1)) {
                answer.deleteCharAt(idx);
                cnt--;
                idx = Math.max(idx - 1, 0);
            }else
                idx++;
        }
        if(cnt != 0){
            return answer.substring(0, answer.length() - cnt);
        }
        return answer.toString();
    }
}

---

처음 코드 (틀림)

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder(number);
        String[] numbers = number.split("");
        Arrays.sort(numbers);
        for(int i = 0; i < k; i++){
            int idx = answer.indexOf(numbers[i]);
            answer.deleteCharAt(idx);
        }
        return answer.toString();
    }
}

-> 원래 작을 수를 삭제하면 최대 값이 나온다고 생각했지만 반례 "4177252841", 4 존재

-> 그리디를 사용 - 어떻게? ... 앞부터 탐색해나가면서 뒷자리가 더 크면 해당 앞자리 삭제 (결국 제일 앞에 있는 수가 크기 좌우하므로) -> 뒷자리 수와 같으면 idx 앞으로 이동

-> 반례) "4321", 1, "432" (자체 내림차순 정렬인 경우) -> 맨 뒤에 k개 자르기

다른 답안 코드 >>> stack을 활용해서 품

- stack에서도 get을 이용하면 넣은 순서대로 출력할 수 있다