[프로그래머스-그리디] 큰 수 만들기 JAVA 자바

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

프로그래머스

 

👉 풀이

• 숫자를 지워서 만들어야 하므로, number.length() - k 자리수가 보장되도록 한 상태에서 큰 수를 만들어야 한다.
• 보장되어야할 자릿수를 남겨두고, 나머지 부분에서 최대값을 찾는다. 그 값을 answer의 앞자리수부터 이어 붙인다.
• 예를 들어 number = "4177252841", k=4
• 현재 뽑아얄할 숫자는 6개이므로, 1개를 뽑더라도 무사히 6자리를 만들 수 있도록 number의 맨 뒤부터 5자리 수는 탐색 범위에서 제외한다.
• "4177252841"에서 "52841"을 제외하고 "41772"에서 가장 큰 수를 찾는다. (탐색 범위: startIdx=0, endIdx=5)
• 7을 뽑고 answer = "7"
• 7의 index 2를 포함 그 전 자리들은 다음 탐색에서 제외 된다.
• "7252841"에서 "2841"을 제외하고 "725"에서 가장 큰 수를 찾는다. (탐색 범위: startIdx=3, endIdx=6)
• 7을 뽑고 answer = "77"
• 7의 index 3를 포함 그 전 자리들은 다음 탐색에서 제외 된다.
• "252841"에서 "841"을 제외하고 "252"에서 가장 큰 수를 찾는다. (탐색 범위: startIdx=4, endIdx=7)
• 5를 뽑고, answer = "775"
• 5의 index 5를 포함 그 전 자리들은 다음 탐색에서 제외 된다. (탐색 범위: startIdx=6, endIdx=8)
• 이렇게 answer.length가 number.length() - k보다 커지지 않을 때까지 반복한다.

public class p42883 {

    public String solution(String number, int k){
        // 처음 숫자 문자열을 탐색하면서 정답 문자열의 앞자리 수 부터 최대값이 되도록 고른다.
        // 정답 문자열은 점점 추가되므로 StringBuilder를 사용한다.
        StringBuilder answer = new StringBuilder("");
        int startIdx = 0;
        int answerlen = number.length() - k;
        int endIdx = k + 1;
        while(answer.length() < answerlen){ // 처음 숫자 문자열 탐색
            int max = 0;
            for(int i = startIdx; i < endIdx; i++){ // 지정한 탐색 범위에서 최대값 선택
                if(max < number.charAt(i) - '0'){
                    max = number.charAt(i) - '0';
                    startIdx = i + 1;
                }
            }
            endIdx += 1;
            answer.append(max);
        }
        return answer.toString();
    }

    public static void main(String[] args){
        String number = "4177252841";
        int k = 4;
        System.out.println(new p42883().solution(number,k));
    }
}

 

---

Source

https://born2bedeveloper.tistory.com/27

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