[Java] k 자리 제거하기

🎈 문제

양의 정수가 담긴 문자열 s 가 있다고 하자. 이 문자열에서 k 개의 숫자를 제거해, 가장 작은 숫자를 만들고자 한다.

이렇게 만든 가장 작은 숫자를 담은 문자열을 출력하시오.

단, k 개의 문자열을 제거한 결과는 앞에 불필요한 0 이 포함될 수 있으며, 최종 출력에는 이 불필요한 0은 제거하여 출력하시오.

 

🎈 입력 설명

• 0 < s.length <= 10000
• 0 < k <= s.length

 

🎈 출력 설명

가장 작은 숫자를 문자열로 반환

 

🎈 입력 예시

s = "105990"

k = 1

 

🎈 출력 예시

"5990"

 

🎈입출력 설명

맨 앞의 '1' 을 제거하면 "05990"이 된다. 불필요한 '0'을 제거한 최종 출력은 "5990" 이다.

 

 

🎈 코드 구현

• 재귀 형태로 구현
  • 주어진 k 만큼 문자를 모두 제거했다면 (k==0 이라면) 리딩 제거를 제거한 후 반환
• 제거할 자릿수 (k)가 문자열의 길이와 같거나 클 때 "0" 반환
• 우선순위
  • 문자열에서 2번째 자리에 0이 있다면 문자 한개를 지움으로써 2개를 지우는 효과 발생하기 때문에 우선순위가 제일 높다
  • 자릿수가 높고 숫자가 큰 숫자를 우선적으로 삭제

 

class Solution {
    public String solution(String s, int k) {

        // 제거할 자릿수가 입력된 문자열의 길이보다 클 때
        // 이때는 0을 반환
        if (k >= s.length()) {
            return "0";
        }

        // 주어진 k만큼 문자를 모두 제거했다면
        if (k == 0) {
            return removeLeadingZero(s);
        }

        char[] chars = s.toCharArray();

        // 2번째 자리가 '0' 이라면 숫자 하나를 지워도 2개를 지우는 효과가 있다.
        // 따라서 다른 숫자를 지우는 것 보다 우선순위가 높다.
        if(chars[1] == '0') {
            return solution(removeLeadingZero(s.substring(1)),k-1);
        } else {
            int idx  = 0;

            // 높은 자릿수부터 탐색 시작, 숫자가 감소하면 멈춤
            // 숫자가 같다면 큰 자릿수 숫자 삭제
            for (int i = 1; i < chars.length ; i++) {
                if(chars[i-1] < chars[i]) {
                    idx = i;
                } else if (chars[i-1] != chars[i]) {
                    break;
                }
            }

            return solution(
                    s.substring(0,idx) + s.substring(idx+1),
                    k-1
            );
        }
    }

    // Leading Zero를 삭제하고 문자열을 반환하는 메서드
    String removeLeadingZero(String s) {
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c != '0') {
                return s.substring(i);
            }
        }
        return "0";
    }
}