[프로그래머스] 큰 수 만들기 (Java)

프로그래머스 큰 수 만들기

문제풀이

완전탐색이 떠오르지만 최악의 경우에 1000000 C 999999 이다. 따라서 완전탐색은 절대 불가하다. 이 문제는 선택할 수 있는 범위 내에서 가장 큰 숫자를 선택해나가는 그리디한 방법으로 풀 수 있다.

• k개를 지우는 문제지만, n = length - k라고 하고 n개를 선택하는 문제로 바꾼다.
• 선택할 수 있는 범위는 선택한 숫자 오른편에 아직 선택해야할 갯수와 같거나 많은 숫자가 남아 있어야 한다.
• 시간 절약을 위해 StringBuilder를 사용한다.

다른 사람들의 풀이를 살펴보니 단순히 i번째 숫자 < i + 1 번째 숫자 인 경우 i 번째 숫자를 지우면 된다.

구현코드

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();
	    
		int cnt = number.length() - k;
        int left = 0;
        int right = number.length() - cnt;
        int max = -1;
        int idx = 0;
        
        while(cnt > 0) {
        	 max = -1;
             for(int j = left ; j <= right ; ++j){
                 int num = number.charAt(j) - '0';
                 if(num > max){
                     idx = j;
                     max = num;
                 }
             }
             sb.append(number.charAt(idx));
             left = idx + 1;
             right = number.length() - --cnt;
        }

        return sb.toString();
    }
}