[프로그래머스/Lv.2] 큰 수 만들기 - Java

문제

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

프로그래머스

 

 

리뷰

그리디(탐욕법) 문제이다.

풀이

주어진 수의 일정 범위에서 가장 큰 수를 각 자리의 값으로 만들면 된다. 이때 그 범위를 지정하는 것이 관건이다.

현재 자리에 들어갈 수를 구하는 범위를 정하기 위해서는 다음과 같은 조건을 고려해야 한다.

• 범위의 시작 인덱스(start)는 이전 자리에 들어간 수의 바로 다음 자리이다.
• 범위의 마지막 인덱스(end)의 뒤에는 아직 값이 정해지지 않은 자리의 개수만큼 수가 남아 있어야 한다.

코드

import java.util.*;

class Solution {
    
    int[] numArr;
    
    public String solution(String number, int k) {
        
        // number 문자열을 각 자리의 값이 담긴 배열 numArr로 변환
        String answer = "";
        String[] splittedAnswer = number.split("");
        numArr = Arrays.stream(splittedAnswer).mapToInt(v->Integer.parseInt(v)).toArray();
        
        // 주어진 숫자의 길이
        int numberLength = number.length();
        // 만들어야 하는 숫자의 길이
        int answerLength = numberLength-k;
        
        // 각 범위에서 최댓값이 각 자리의 값이 된다.
        int start = 0;
        int end = numberLength-answerLength;
        for(int i=0;i<answerLength;i++) {
            int maxIndex = getMaxIndex(start, end);
            answer+=numArr[maxIndex];
            
            start = maxIndex+1;
            end = number.length()-(answerLength-i-1);
        }
        
        
        return answer;
    }
    
    // start~end 범위에서 최댓값의 인덱스를 구하는 메서드
    private int getMaxIndex(int start, int end) {
        
        int maxIndex = start;
        for(int i=start;i<end+1;i++) {
            if (numArr[maxIndex] < numArr[i]) {
                maxIndex = i;
            }
        }
        
        return maxIndex;
    }
}