[프로그래머스] 큰 수 만들기

코드 힌트

1. 큰 수 만들기:
   • 주어진 숫자에서 일부 자릿수를 제거해 가능한 가장 큰 숫자를 만들어야 합니다.
   • 제거할 자릿수는 이미 고정되어 있기 때문에, 각 자릿수에서 최선의 선택을 해야 합니다.
2. 탐색 방법:
   • 각 자리에서 남은 숫자들 중에서 가장 큰 숫자를 선택합니다.
   • 선택한 숫자의 다음 위치부터 다시 탐색을 시작하여, 그 뒤에서 또 가장 큰 숫자를 찾습니다.
3. 범위 관리:
   • 현재 자리를 결정할 때, 앞으로 선택할 자리를 고려하여 탐색 범위를 설정합니다.
   • 한 번 선택된 숫자는 다시 선택하지 않도록 다음 선택할 범위를 줄여 나가야 합니다.
4. 최적화 아이디어:
   • 이미 선택된 숫자보다 더 작은 숫자는 무시하고, 그 다음 탐색부터 빠르게 넘어가면서 최종 큰 수를 만들어냅니다.

 

---

정답은 더보기 클릭

class Solution {
    public String solution(String number, int k) {
        StringBuilder result = new StringBuilder();  // 결과 문자열을 저장할 StringBuilder 객체
        int s = 0;  // 탐색을 시작할 인덱스
        int e = number.length() - k;  // 최종적으로 뽑아야 할 자릿수 (전체 길이 - 제거해야 할 자릿수)

        // 결과 문자열의 길이만큼 반복 (e는 뽑아야 할 숫자의 총 길이)
        for (int i = 0; i < e; i++) {
            char maxNum = '0';  // 현재 선택할 수 있는 최대 숫자를 저장할 변수
            
            // 현재 위치부터 남은 범위까지 중에서 가장 큰 숫자를 찾음
            // s는 탐색 시작 위치, k + i는 현재 자릿수 기준으로 가능한 최대 범위
            for (int j = s; j <= k + i; j++) {
                if (number.charAt(j) > maxNum) {  // 더 큰 숫자를 찾으면 갱신
                    maxNum = number.charAt(j);
                    s = j + 1;  // 선택된 숫자 다음 인덱스부터 다시 탐색 시작
                }
            }
            
            result.append(maxNum);  // 가장 큰 숫자를 결과에 추가
        }

        return result.toString();  // 완성된 문자열 반환
    }
}