Today's Algorithm(2018-12-31)

programmers. 큰 수 만들기

그리디(탐욕법) 문제라 그랬을까요. 무조건 큰 수를 먼저 골라내거나, 가장 작은 수를 빼내려고만 생각했던 것 같습니다. 탐욕법이 가장 유리해보이는 것을 가장 먼저 고려하는거잖아요. 그렇게 여러 가설을 세우고 이렇게 하면 모든 경우에 대해 적용이 될 수 있는지 탐험해보았습니다.

 

첫번째 가정

• 가장 작은수부터 지워나갑니다.
• 지울 수 있는 대상이 여러 개이고, 지울 수 있는 대상이 그 보다 작다면 앞의 수부터 지웁니다.

문제점 : "4177252841"와 같은 케이스를 걸러내지 못합니다.

 

두번째 가정

• 제일 큰 수부터 순서는 지키면서 앞의 순서대로 가져옵니다.

문제점 : 여전히 "4177252841"와 같은 케이스에서 문제이며 이때는 마지막 수 1이 문제입니다. 큰 수부터 가져온다고 대수는 아니죠.

 

이 문제를 풀면서 가장 고마웠던 것이 "4177252841"였고 가장 나빴던 것도 "4177252841"였습니다. 그 이유는 이 테스트 데이터 덕분에 제가 고려하지 못했던 것을 미리 고려하게 해줬다는 것이고 나빴던 것은 어떻게 이걸 해결해야 할지 모르겠다는 것이죠.

 

해결

버스를 타고 오다가 다른 사람의 알 수 없는 코드를 보았고 앞뒤로 인덱스를 비교를 하는 것을 보았습니다. 아..!! 탐욕법이라 가장 큰 수 또는 가장 작은 수만 고려했었는데 이 문제의 본질은 결국 큰 수를 만드는 것이고 가장 큰 수가 만들기 위해선 앞부분(단위수가 큰 부분)이 중요합니다.

이 말은 뒤가 어떻게 되었든 앞이 무조건 잘되어있으면 뒤는 신경써도 되지 않아도 된다는 것이죠. 그렇기 때문에 하나씩 지워나갈 때 가장 윗부분부터 sb.charAt(i) < sb.charAt(i + 1) 의 경우 인 경우 i 인덱스의 숫자를 지우는 것입니다. 사실 이렇게 보면 그리디에서의 해결법, 각 단계에서 최선의 선택(유리한 선택)이 이 경우였겠네요. 제가 포인트를 잘못 잡았던 것 같아요. 그래서 코드를 살펴보면 다음과 같습니다.

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder(number);
        while (k > 0) {
            boolean deleted = false;
            for (int i = 0; i < sb.length() - 1; i++) {
                if (sb.charAt(i) < sb.charAt(i + 1)) {
                    sb.deleteCharAt(i);
                    deleted = true;
                    break;
                }
            }
            if (!deleted) sb.deleteCharAt(sb.length() - 1);
            k--;
        }
        return sb.toString();
    }
}

다만 13째줄이 필요한 이유는 "7777777"과 같이 모든 수가 같은 경우도 존재할 수 있겠죠. 이때는 지워진 수가 없는데요. 이 경우 뭐든 지워줘야하니 제일 마지막 인덱스 수를 지워주도록 하였습니다!