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

오백만년만에 알고리즘 문제를 풀었다. 원래 leetcode를 이용할 계획이었지만, 랜덤으로 문제를 뽑았을 때 자꾸 medium 단계가 나와서 프로그래머스 간단한 문제로 방향을 바꿨다. 이 쉬운 2단계 문제를 푸는데도 한참 걸렸다. 열심히공부해야지ㅠㅠㅠㅠㅠㅠ

첫번째 문제 해결방법은 한 수를 지웠을 때 가장 큰 수를 남기고 같은 방식으로 진행하는 방법이었다. 당연히 시간초과 ㅋㅋ

일단 코드는 아래와 같습니다.

public String solution(String number, int k) {
        for (int deleteCount = k - 1; deleteCount >= 0; deleteCount--) {
            String bigNumber = "0";

            for (int i = 0; i < (number.length() - deleteCount); i++) {
                String tempNumber = copyString(number, i);
                if (tempNumber.compareTo(bigNumber) > 0) bigNumber = tempNumber;
                // 원래 Integer.parseInt 를 사용해서 비교를 헀는데 문제에 1,000,000자리인 수라고 되어있음 -> 9자리만 넘어도 런타임에러;
                // 이렇게 수정해서 일단 런타임에러는 해결
            }

            number = bigNumber;
        }

        return number;
    }

    String copyString(String number, int index) {
        String result = "";

        for (int i = 0; i < number.length(); i++) {
            if (i != index) result += number.charAt(i);
        }

        return result;
    }

시간초과의 주범인 스트링카피가 없는 풀이 방법을 생각해봤다.

기존 스트링에서 k개의 수를 지운다 == (length - k)개의 수를 뽑는다

요생각으로 문제풀이를 시작했다. 위의 풀이와 같이 앞으로 뽑아야하는 숫자들은 제외한 범위에서 가장 큰 수를 뽑는 방식으로 해결했다. 코드는 아래와 같습니다.

public String solution(String number, int k) {
        int pos = 0;

        StringBuilder answer = new StringBuilder();

        for (int left = (number.length() - k) - 1; left >= 0; left--) {
            char bigNum = '0';

            for (int i = pos; i < (number.length() - left); i++) {
                if (bigNum < number.charAt(i)) {
                    bigNum = number.charAt(i);
                    pos = i + 1;
                }
                if (bigNum == '9') break;
            }

            answer.append(bigNum);
        }

        return answer.toString();
    }