프로그래머스 <큰 수 만들기>

문제

숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 수를 구해라

k개의 수를 제거해도 수 안에서의 순서는 똑같다

접근

k번만큼 for문을 돌린 뒤 한 번 더 for문을 돌려 number를 맞춰준다.
이 때 앞의 수가 뒤의 수보다 작을 경우 없애주는 것이 더 큰 수를 만들 수 있다.

풀이

public String solution(String number, int k) {
        for (int i = 0; i < k; i++) {
            String a = number;
            for (int j = 0; j < number.length() - 1; j++) {
                if (number.charAt(j) < number.charAt(j + 1)) {
                    number = number.substring(0, j) + number.substring(j + 1, number.length());
                    break;
                }
            }
            if (number == a) number = number.substring(0, number.length() - 1);
        }
        return number;
}

예... 테스트 10이 매우 긴가봅니다 실패했습니다.

접근

다른 방법이 무엇이 있을까 생각해보다가 String보다 StringBuilder를 사용하는 것이 시간을 절약하는데 도움이 된다고 하여 써보았다.

이 때 StringBuilder에는 deleteCharAt(i)를 통하여 i번 index에 있는 문자를 제거해줄 수 있는 편한 기능이 있다.

풀이

class Solution {
    public String solution(String number, int k) {
        StringBuilder str = new StringBuilder();
        str.append(number);
        for (int i = 0; i < k; i++) {
            String a = str.toString();

            for (int j = 0; j < str.length() - 1; j++) {
                if (str.charAt(j) < str.charAt(j + 1)) {
                    str.deleteCharAt(j);
                    break;
                }
            }

            if (a.equals(str.toString())) str.deleteCharAt(str.length()-1);
        }
        return str.toString();
    }
}

하지만 또 같은 테스트10에서 실패하였다.

접근

마지막으로 Stack을 쓰는 방법이 있을 것 같다.

풀이

class Solution {
    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < number.length(); i++) {
            char ch = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < ch && k-- > 0) {
                stack.pop();
            }
            stack.push(ch);
        }
        for (int i = 0; i < result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }
}

stack에 들어있는 값이 ch값보다 작으면 꺼내고, 이것을 k가 0이 될 때까지 반복한다.