프로그래머스 큰 수 만들기(그리디)

큰 수 만들기

​

문제 설명

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

나의 풀이 인데 통과는 했지만 오류가 있는것 겉다

 

import java.util.Arrays;

class Solution {
	
	


	public String solution(String number, int k) {
    	//number의 숫자가 수어졌을 때 k개 숫자를 빼을때 최대의수 
    	
    	String num[] = number.split("");
    	int tmp[] = new int[num.length];
    	for(int i = 0 ; i < num.length; i++) {
    		tmp[i] = Integer.parseInt(num[i]);
    		
    	}
    	StringBuilder sb= new StringBuilder();
    	
    	for(int i = 0 ; i < tmp.length;i++) {
    		
    		if(k != 0) {
	    		for(int j = i+1 ; j <=i+k;j++) {
	    			
	    			if(i+k == tmp.length) {
	    				k = 0;
	    				break;
	    			}else if(tmp[i] < tmp[j]) {
	    				//현재위치부터 나머지의 길이가 k와 같나? 아니면 break; 맞으면 나머지append;
	    				// 큰게 있으면 그수를 뺀것이므로 k를 k-1 해주고 break;
	    				// 하지만 남은자리수가 k수랑 같으면 완전히 break;
	    				// 모두 같은수일때 처리해주어야함
	    				
	    		
	    				
	    				k = k-1;
	    				break;
	    			}else if(tmp[i]>=tmp[j] && j ==i+k){
	    				sb.append(tmp[i]);
	    			}
	    			
	    		}
    		}else {
    			
    			sb.append(tmp[i]);
    	}
    		
    	}
    	
    	
    	
    	
        String answer = sb.toString();
        return answer;
    }
}

 

 

최적 풀이(해석해보기)

 

import java.util.Stack;
class Solution {
    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();

        for (int i=0; i<number.length(); i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                stack.pop();
            }
            stack.push(c);
        }
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }
}