프로그래머스 LV2. 큰 수 만들기 (자바)

🍀 문제

어떤 숫자에서 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"

 

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

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

 

😊 나의 코드

class Solution {
    public String solution(String number, int k) {
        String answer = "";
		while(k>0) {
			if(k>=number.length()) {
				return answer;
			}
			int maxIndex = 0;
			for(int i=0; i<=k; i++) {
				if(Character.getNumericValue(number.charAt(maxIndex)) < Character.getNumericValue(number.charAt(i))){
					maxIndex = i;
				}
			}
			k -= maxIndex;
			answer += number.charAt(maxIndex);
			number = number.substring(maxIndex+1, number.length());
		}
        return answer + number;
    }
}

 

 

하지만.. 테스트 10에서 계속 시간초과가 떠서 StringBuilder로 다시 풀었다.👇

class Solution {
    public String solution(String number, int k) {
        StringBuilder num =new StringBuilder(number);
        int startIndex = 0;
        while(k>0) {
            if(k>=num.length()-startIndex) {
                num.delete(startIndex, num.length());
                return num.toString();
            }
            int maxIndex = startIndex;
            int max = num.charAt(maxIndex);
            for(int i=startIndex+1; i<=k+startIndex; i++) {
                if(max < num.charAt(i)) {
                    maxIndex = i;
                    max = num.charAt(i);
                }
            }
            k -= (maxIndex-startIndex);
            num.delete(startIndex, maxIndex);
            startIndex++;
        }

        return num.toString();
    }
}

겨우 통과!!

시간초과가 젤 어려운거 같다...ㅠ.ㅠ

문제 자체는 어렵지 않았는데, 시간초과를 해결하느라 오래걸렸다...ㅎㅎ