28. LEVEL 2 - 큰 수 만들기- Greedy

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

코딩테스트 연습 - 큰 수 만들기

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        
        char[] numbers = number.toCharArray();
        int digit = number.length() - k;	// 자릿수
        
        int i = 0;	// 탐색범위 시작
        int j = numbers.length - digit;	// 탐색범뉘 끝
        
        while(j < numbers.length) {
        	int max = -1;	// max = 0 으로 하면 배열에 0만 있는 경우 최대값 추출 불가능
        	int index = 0;
        	for (int n = i; n <= j; n++) {	// 추출대상 구간의 최대값 + 인덱스
        		if(numbers[n] - '0' == 9) {	// 9면 무조건 최대이므로 break
        			max = 9;	
					index = n;
					break;
        		}        		
				if(numbers[n] - '0' > max) {
					max = numbers[n] - '0';	
					index = n;
				}
			}        
        	answer.append(numbers[index]);	// 결과 기록
            
        	i = index + 1;	// 탐색 범위 변경
        	j++;
        }
        return answer.toString();
    }
}

 

- 7자리의 수에서 3개를 제거하면 결과는 4자리의 수임

- 최초의 순서는 유지해야 하므로, 맨 앞 자릿수부터 후보가 되는 범위를 찾고, 그 범위 안에서 최댓값을 고르면 됨

- 다음 순번에는 선택된 숫자 다음부터 시작해서 탐색을 시작