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

아이디어

그리디

 

풀이

먼저, 큰 수를 유지하려면 앞쪽에 나오는 수가 뒤쪽에 나오는 수보다 커야한다. 

현재 수를 기준으로 현재 수가 다음 수보다 큰 지는 알 수 없으므로 현재 수는 answer에 무조건 추가한다.

(현재 수와 answer의 수들만 비교할 것이다.)

 

처음에는 현재 수가 answer의 마지막 수보다 큰 경우 마지막 수를 제거하는 방식으로 접근했다.

그러나 이 방식에서는 answer의 제거된 수 앞에 현재 수보다 작은 수가 여전히 남아있을 경우 최적해를 가질 수 없게 된다.

그래서 answer의 마지막 인덱스부터 순회하여 현재 수보다 작은 수가 존재한다면 이를 모두 제거하도록 하였다.

 

만약 제거된 수가 k보다 작다면, 이는 추가된 수 앞에 이보다 작은 수가 없어서 제거 없이 계속 추가된 경우이다. 

그러므로 answer 뒷부분의 최소 k - cnt 개의 수들은 내림차순으로 구성되므로,

뒷부분의 k - cnt개의 수를 모두 제거하여 최적해를 구할 수 있다. 

 

그리고 String으로 푸니 시간이 너무 오래 걸려서 StringBuilder를 사용했다.

 

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        int len = number.length(), cnt = 0;
        StringBuilder sb = new StringBuilder("");

        for(char x : number.toCharArray()) {
            if(sb.equals("")) {
                sb.append(x);
                continue;
            }
            int cur = Integer.parseInt(x + "");

            while(sb.length() > 0){
                int prev = Integer.parseInt(sb.charAt(sb.length() - 1) + "");

                if(prev < cur && cnt < k) {
                    sb.deleteCharAt(sb.length() - 1);
                    cnt++;
                } else break;
            }
             sb.append(x);
        }

        String answer = sb.toString();
        if(cnt < k) answer = sb.substring(0, sb.length() - (k - cnt)).toString();

        return answer;
    }
}