[프로그래머스] 탐욕 알고리즘 - 큰 수 만들기

public static String solution(String number, int k) {
        String answer = "";
        
        char[] chs=number.toCharArray();
        int[] nums=new int[number.length()];
        int max_index=0; 
        int l=number.length();
        int left=0;		//남은 제거할 수
        
        //가능한 앞자리 중 가장 큰 수 찾기
        for(int i=0;i<chs.length;i++) {
        	nums[i]=chs[i]-'0';	// 문자 -> 숫자
        	max_index=(nums[max_index]<nums[i] && i<=k)i:max_index; 
        }
        
        left=max_index;	// max_index앞 모든 수 제거
        
        for(int i=max_index;i<l-1;i++) {
        	if(answer.length()==l-k) break;	//정답인 상태라면
        	// 다음 숫자가 더 크고 제거할 것이 남았다면
        	if(nums[i]<nums[i+1] && left<k) {	
        		left++;		//제거 추가
        		continue;	//다음 숫자로 넘어가기
        	}
        	else {
        		// 가장 큰 수로 출력하기 위해 앞의 0들은 제거
        		if(answer.length()==0 && chs[i]-'0'==0) continue;
        		answer+=chs[i];
        	}
        }
        
        //정답이 완성되지 않았다면 마지막 값 추가
        if(answer.length()!=(l-k)) answer+=chs[number.length()-1];
        
        return answer;
    }

진짜 여러 상황 테스트 케이스에 추가하고, 다른 사람이 질문 올린 것을 보면서 예외처리도 했지만... 

테스트 케이스 11,12 번을 빼면 모두 실패한다...

진짜 왜그런지 모르겠다....

 

 

코드 설명

1. 모든 문자열을 후보로 두고.. 가장 앞자리에 올 가장 큰 수를 먼저 찾는다

-> 이 큰 수는 k보다 인덱스가 작은 수 중 가장 큰 수 이다.

2. 큰 수 앞의 숫자들은 제거한다. 

-> left 변수 증가

3. 큰 수 오른쪽을 차례차례 보며 num[i]<num[i+1]을 만족할 때 인덱스를 증가시킨다.

즉, num[i]를 제거한다.

4. 정답 크기를 만족했거나, k만큼 제거한 상태라면 반복문을 나와 정답을 출력

 

 

정답인 다른 사람 풀이 ㅠㅠ

 

 

스택을 사용하여 해결

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);
    }
}

 

 

내 풀이랑 사고가 비슷해 보여 가지고 왔다.

public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        
        int idx = 0;
        int comp = 0;
        for(int i=0; i<number.length()-k; i++){
            comp = 0;
            for(int j=idx; j<=i+k; j++){
                if(comp < number.charAt(j)-'0'){
                    comp = number.charAt(j)-'0';
                    idx = j+1;
                }
            }
            answer.append(comp);
        }
        return answer.toString();
    }

 StringBuilder를 사용하여 문제를 해결하였는데,

아마 처리 시간도 빠르고 문자를 제거하는 데 편리해서 사용한 것 같다..

 

 

StirngBuilder 관련해서 블로그 정리 글

https://ifuwanna.tistory.com/221