[Programmers Lv2, Java] 큰 수 만들기

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

---

처음에는 별 생각없이 int로 만들다가 실행시켰더니  런타임에러로 쭈루룩 뜨길래 바로 String으로 고쳤다.

초반에 한 30분정도 계속 String을 정수형이라고 생각하고 비교하는 식으로 만들었는데,

테케6~11이 계속 실패가 떠서 고민하다가

문제 카테고리가 그리디알고리즘으로 되있길래 앞에서부터 잡아먹는 방식으로 생각해봤다.

public String solution(String number, int k) {
        for (int index = 0; index < number.length() - 1; index++) {
            if (k <= 0) break;
            char indexValue = number.charAt(index);
            char nextValue = number.charAt(index + 1);
            if (indexValue < nextValue) {
                number = number.substring(0, index) + number.substring(index + 1);
                index = -1;
                k -= 1;
            }
        }

        return number;
    }

처음 만든 코드는 위와 같다.

이 코드는 테케10 타임아웃, 테케12 실패가 뜨는 코드인데,

현재위치의 숫자보다 다음위치의 숫자가 더 크면 현재 위치의 숫자를 지워야 숫자가 커진다는 기본 전제를 바탕으로 진행하였고, 각 문자를 바꿀 때 마다 index가 0으로 돌아가서 처음부터 다시 검사한다.

 

여기서, 삭제 조건이 다음글자와의 비교기 때문에 for문의 끝이 number.length()-1로 되어있는데 그래서 마지막 문자를 삭제해야될 경우를 해결하지 못했다.

※ 반례 : 입력 (91, 1) 일경우 1을 삭제해야하는데 이를 삭제하는것이 구현되지 않음.

 

이를 해결 하기 위해 k > 0이면 마지막 글자를 지우는 코드를 추가해서 테케12를 해결했다.

        if(k > 0) {
            number = number.substring(0, number.length()-1);
        }

 

하지만 테케10은 여전히 타임아웃이고,

타임아웃이 나왔다는건 1. 처리시간이 길거나, 2. 무한루프에 빠졌거나 둘 중 하나라고 생각됬다.

근데 무한루프에 빠질 일은 잘모르겠어서, 처리시간에 집중해봤다.

IDE상에서 100만 Length의 숫자를 Length-1로 돌려봤는데 1분이 넘어도 결과가 안나왔으므로, 이런 큰 숫자의 경우를 빠르게 처리하지 못하는것이 문제로 보인다.

(사실상 찾을때마다 index가 0으로 초기화되니, 최악의 경우 O(N^2)이므로...)

 

그래서 생각해보니 index를 0으로 돌릴필요없이, -2를 하면 된다는 생각이 들었다.

예를 들어 417...을 테스트할 때,

4->1 clear ( index = 0 )

1->7 remove 1 ( index = 1 )

변한 문자열은 47, index =2가 되므로

4->7을 테스트하려면 index 0으로 돌아가야하고, 이경우 -2가 되면된다.

 

해당 라인을 추가한 후, IDE 상에서 900,000 Length 문자열에 대한 k=90,000이 소요된 시간이 약 45초였다.

1시간 가량 헤매다가 영 답답해서 질문하기란을 한 번 구경해봤는데 9를 패싱하는 코드를 넣으라는 말이 있었다.

그러나 내 알고리즘에서는 9를 패싱하는것이 의미가 별로 없어서 ( 어차피 index<next면 continue되는것이나 마찬가지니까) 적절하지 않았다.

 

문제가 될법한 부분은 substring을 2번씩 사용하는것이 처리속도에 지장이 있지않을까 해서, char[]을 사용해보려고 했는데, java array는 index를 통해 삭제가 불가능하다보니 List<String>으로 시도해봤다.

 

    public String solution(String number, int k) {

        List<String> chars = new ArrayList<>(Arrays.asList(number.split("")));

        for (int index = 0; index < chars.size() - 1; index++) {
            if (k <= 0) break;
            char indexValue = chars.get(index).charAt(0);
            if(indexValue == '9') continue;
            char nextValue = chars.get(index+1).charAt(0);
            if (indexValue < nextValue) {
                chars.remove(index);
                index -= 2;
                if(index < 0) index = -1;
                k -= 1;
            }
        }

        if(k > 0) {
            chars.remove(chars.size()-1);
        }

        StringBuilder result = new StringBuilder();
        for(String str : chars) result.append(str);

        return result.toString();
    }

 

이것으로 45초걸리던게 8.2초로 크게 감소됬다.

물론 아직도 테케10은 시간초과가 뜨고있었고... 문자열을 합치는것도 for를 쓰지않고 해보기로했다.

        String charToString = chars.toString();
        String result = charToString.substring(1, charToString.length()-1).replace(", ", "");

1%정도의 속도향상이 있었으나, 아직 많이 부족했다.

 

해도해도 해결이 안되길래 그냥 맘먹고 char[]로 구현했다.

    public String solution(String number, int k) {

        char[] chars = number.toCharArray();

        int befIndex;
        for (int nextPos = 1 ; nextPos < chars.length && k > 0 ;) {
            befIndex = nextPos;
            while(befIndex > 0 && chars[--befIndex] == 0); // chars[--befIndex]가 0이면 0이 아닐때까지 거슬러 올라감. ( nextPos 1일때 0...)

            if(befIndex == 0 && chars[befIndex] == 0) { // 뒤쪽 인덱스에 비교할 곳이 없는 경우
                nextPos += 1;
                continue;
            }

            if(chars[befIndex] < chars[nextPos]) { // 비교 결과 뒤쪽 인덱스가 현재 위치 인덱스보다 작은 경우, 뒤쪽 인덱스를 0으로 만들고 뒤쪽 추가 탐색
                chars[befIndex] = 0;
                k -= 1;
            } else { // 뒤쪽 인덱스와 현재 인덱스 값이 같은 경우 다음 탐색
                nextPos += 1;
            }
        }
        
        if(k > 0) chars[chars.length-1] = 0; // TC-12 Exception (마지막 글자를 지워야하는 경우)

        StringBuilder toString = new StringBuilder();
        for(char c : chars) if(c > 0) toString.append(c);

        return toString.toString();
    }

시간초과로 괴롭히던 TC-10이 22ms만에 클리어 된 모습이다.

속도가 필요할땐 Array를 써야겠다..

 

※ 이 문제에만 거의 2시간정도 썼는데, 다른 사람 풀이 가보니까 전부 스택으로 풀었더라.

코드 이쁜거 몇개 넣어봤는데 이 코드보다 느린것들이 대부분이라 내가 이긴걸로 치자.

아무튼 내가 이긴거임...