[Algorithm] 프로그래머스 큰 수 만들기 자바 풀이, 그리디 알고리즘

안녕하세요! 오늘도 열심히 달리고 있는 젤리킹입니다. 이번에 풀어볼 문제 유형은 그리디 알고리즘으로 처음에는 무엇으로 풀어야 하나 많은 고민을 하였습니다.

 

문제

 

문제 해결 아이디어

해당 문제는 제가 작성한 코드가 테스트 케이스에서 계속 실패하여 다른 사람의 코드를 참조하였습니다.

 

• k가 주어지면 적어도 k 인덱스 부분부터는 꼭 숫자를 선정해줘야 한다.
• 숫자를 선택하면 선택한 인덱스 j 부터 k+1까지 숫자를 뽑아줘야 한다.
• 숫자를 선택할 때 설정한 범위 내에서 최대값을 뽑아준다.
• 해당 범위에서 선정된 최대 숫자를 answer에 더해준다.

 

자바 코드

 

package com.company;

import java.util.*;

public class Main {

    public String solution(String number, int k) {
        int idx = 0;
        char max;
        StringBuilder answer = new StringBuilder();

        if(number.charAt(0) == '0') return "0";
        for(int i = 0; i < number.length() - k; i++) {
            max = '0';
            for(int j = idx; j <= k + i; j++) {
                if(max < number.charAt(j)) {
                    max = number.charAt(j); idx = j + 1;
                }
            }
            answer.append(max);
        }
        return answer.toString();
    }


}