프로그래머스 lv2 큰 수 만들기

문제 링크

큰 수 만들기

풀이

• 만들어야 하는 수의 길이는 k개를 제외한 개수이기에, number.length() - k라고 할 수 있다.
• 그리고 만들어지는 수는 개중에 가장 큰 수여야 하기에 앞자리수가 가장 '커야만' 한다.
• 숫자를 제거하는 방식이기에 숫자의 순서를 재조합해서 순서를 뒤바꾼 다음에 만드는 큰 숫자는 의미가 없다.

다음과 같은 숫자를 예를 들어서 문제 로직을 풀이해보자.

nubmer = 1231234, k = 3

• 뽑아야하는 숫자는 7-3이므로 4개이다.
• 숫자를 앞에서 한 개만 뽑아도, 나머지 숫자로 완성할 수 있도록 뒤에서 3자리수는 남겨둔다.(234)
• 뒤의 숫자(234)를 제외한 나머지 숫자에서 가장 큰 수를 찾는다.(1231)
• 여기서 가장 큰 숫자는 3이고, 뽑은 3은 리턴값에 붙여준다.
• 3의 인덱스는 2이므로, 인덱스가 0, 1인 것들은 전부 날린다.
• 앞에서 한자리를 뽑았기에, 우리가 뽑아야하는 숫자는 3개이다.
• 그렇기에 3개에서 1개만 뽑아도 정답 4자리수를 만들 수 있으므로, 우리는 앞에서 처리되고 남은 숫자(1234)에서 뒤의 2자리는 제거한다. (34)
• 그렇게 하면 앞에 남은 숫자는 12 이고, 여기서 가장 큰 수를 구한 뒤, 리턴값에 더한다.(리턴값 = 32)
• 그 뒤로도 동일한 로직으로 앞의 숫자 버리고, 나머지 숫자에서 가장 큰 수를 뽑는다.
• 그렇게 하면 3234 가 최종 리턴값이 되며 이 숫자가 구할 수 있는 숫자중에 가장 큰 수라고 할 수 있다.

위 로직을 통해서 코드를 짰을 때, 아래처럼 구현할 수 있다.

class Solution {
    
    public String solution(String number, int k) {
        return greedy(number, k);
    }

    public static String greedy(String number, int k) {
        StringBuilder answer = new StringBuilder();
        int n = number.length() - k; // 뽑아야하는 숫자의 수
        int start = 0;

        while (start < number.length() && answer.length() != n) {
            int leftNum = k + answer.length() + 1; // 남아있어야 하는 숫자 개수.
            int max = 0;
            for (int i = start; i < leftNum; i++) {
                int charAtNum = number.charAt(i) - '0'; // char에서 숫자를 구하는 방법 
                if(max < charAtNum) {
                    max = charAtNum;
                    start = i + 1;
                }
            }
            answer.append(max);
        }
        return answer.toString();
    }
}

소감

• 처음에는 nCr, 즉 조합문제인지 알고 풀었다가, 죄다 런타임 에러가 났다 ^^;
• 왜인가 했더니 범위로 주어진 수가 2자리 이상, 1,000,000자리 이하인 숫자. 중간에 String 을 Integer로 변환하고 그러니 런타임 에러가 날 수 밖에..
• 문제를 stack 으로 풀었다는 이야기를 듣고 해보았으나, 위의 근본적인 문제를 바꾸지 않는다면 해결되지 않았다.
• 이 문제 역시 규칙성을 찾아내야만 했다.
• 아는만큼 보인다고 했다. 열심히 풀어보자.