[프로그래머스] 큰 수 만들기(level 2, Greedy)

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

 

class Solution {
	public String solution(String number, int k) {
		String answer = "";
        
		int idx = 0;
		StringBuilder sb = new StringBuilder();
		
		// 앞에서 부터 (전체길이 - k) 수 중 가장 큰 수 선택
		// 선택한 수 다음 인덱스 부터 탐색 범위를 한칸씩 늘려가며 반복 탐색
		for(int i = 0; i < number.length() - k; i++) {
			char max = 0;
			for(int j = idx; j <= i + k; j++) {
				if(max < number.charAt(j)) {
					max = number.charAt(j);
					idx = j + 1;
				}
			}
			sb.append(max);
		}
        
        return sb.toString();
    }
}

 

문자열의 특정 범위 내에서 가장 큰 문자를 반복적으로 선택해서 결과 문자열을 만드는 코드이다.

 

반복문으로 남길 문자열의 각 자리 수를 결정한다.

i는 현재 위치에서 k를 포함한 범위 안에서 최대 문자를 찾기 위한 인덱스이며

idx는 현재 탐색의 시작 위치이다.

max는 현재 위치에서 가장 큰 문자를 저장하는 변수이다.

 

내부 반복문은 idx부터 i + k 까지 문자를 확인해서 가장 큰 문자를 찾는다.

i + k를 문자 탐색의 마지막 범위로 하는 이유는 뒤에 남길 문자를 고려해야 하기 때문이다.

이때 큰 문자를 찾으면 max를 갱신하고 idx를 현재 문자의 다음 인덱스로 업데이트 한다.

 

 

참고

https://hyojun.tistory.com/entry/프로그래머스-큰-수-만들기-Java