[프로그래머스(Programmers)][자바(java)] (Lv2) 큰 수 만들기

 

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

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

 

 

문제 설명

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

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

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

 

제한 조건

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

 

입출력 예

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

 

 

문제 풀이

 

public class Solution {

	public String solution( String number, int k ) {

		StringBuilder sb = new StringBuilder();
		int len = number.length(), idx = 0, i, j;
		char max, num[] = number.toCharArray();
		for (i = 0; i < len - k; i++) {
			max = '0';
			for (j = idx; j <= k + i ; j++) {
				if (max < num[j]) {
					max = num[j];
					idx = j+1;
				}
			}
			sb.append(max);
		}
		return sb.toString();
	}

}

 

k개를 제거해야 한다는 것은 (전체개수 - k) 개를 선택하는 것과 같음

(전체개수 - k)개 만큼 선택할 때까지 루프 수행 ( for i )

String number에서 선택해야 하는 개수만큼 오른쪽 숫자들을 제외하고 제일 큰 숫자를 찾음

시작 인덱스는 초기에 0, 끝 인덱스는 ( 제거할 글자 수( k ) + 선택한 글자 수( i ) ) 이다.

숫자를 찾은 후에는 그 인덱스 + 1이 시작 인덱스가 됨 

반복하며 가장 큰 수를 구함