프로그래머스 Lv.2) 큰 수 만들기 (Greedy)

큰 수 만들기

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

풀이

 

고득점 Kit 중 greedy에 해당하는 문제다. 이 문제는 전에 풀었었는데, 다시 풀기에 실패한 문제다.

Lv2지만 체감상 Lv3였다.. 도저히 모르겠어서 전에 풀었던 코드를 봤는데, 내 머릿속에서 나온 코드가 아닌 것 같다.

그래서 다른 분들의 풀이를 보고 다시 풀었다.

 

두 풀이 모두, 탐색 범위를 변경해가면서 가장 큰 갑을 넣어주는 로직이다.

가장 큰 값을 찾았을 때, 앞에 있는 수를 모두 지울 수 있다면 답에 더해주고, 아니면 범위를 재설정하는 방법이다.

count를 소진할 때 까지 진행하면서, 답을 찾는다.

 

start, end 그리고 max와 maxIdx를 설정해주는 이유는, 완전탐색의 경우 시간초과가 뜨기 때문이다.

시간초과가 우려될 때, 이중 반복에서 경우의 수를 줄여주는 방법에 익숙해지자.

그리고 시험 때는 최악의 경우인 테스트케이스는 주어지지 않기 때문에, 문제를 풀고 검증하기 전에 최악의 경우를 추가해서

확인해보는 습관을 들이자.

 

 

코드 1

 

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int len = number.length();

        StringBuffer sb = new StringBuffer();

        int count = len -k;
        char max = number.charAt(0);
        int maxIdx=0, lastIdx = len, start =0;

        while(count >0) {
            for(int i=start; i<lastIdx; i++) {
                char ch = number.charAt(i);
                if(max < ch) {
                    max = ch;
                    maxIdx = i;
                    if(max =='9') {
                        break;
                    }
                }
            }

            if(len-maxIdx < count) {    // 앞에서 지울 수 있는 범위를 넘어가는 수가 MAX일 경우 재설정
                lastIdx = maxIdx;
                max = number.charAt(start);
                maxIdx = start;
            } else {
                sb.append(max);
                if(maxIdx < len-1) {    // out of index 방지
                    maxIdx++;           // 최고값 다음 수부터 탐색
                    max = number.charAt(maxIdx);
                    start = maxIdx;
                    lastIdx = len;
                }
                count--;
            }
        }
        answer = sb.toString();

        return answer;
    }
}

 

코드 2

 

class Solution {
    final char ZERO = '0';
    
    public String solution(String number, int k) {
        return getAnswer(number, k);
    }
    
    private String getAnswer(String number, int k) {
        StringBuffer sb = new StringBuffer();
        int len = number.length();
        int idx =0;
        for(int i=0; i<len-k; i++) {
            char max = ZERO;
            for(int j=idx; j<=i+k; j++) {
                char ch = number.charAt(j);
                if(max < ch) {
                    max = ch;
                    idx = j+1;
                }
            }
            sb.append(max);
        }
        return sb.toString();
    }
}