[자바] 프로그래머스 - 큰 수 만들기 (Level 2)

🔗 문제 링크

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

📝 문제 설명

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

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

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

⚠️ 제한사항

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

🖨 입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

📂 분류

그리디, 스택

💡 풀이

처음 접근 방식은 조합이었다. 하지만 제한 조건을 보니 최대 _1,000,000C_500,000가지가 되기 때문에 이 방법으론 해결할 수 없었다.

처음 시도한 코드

import java.util.*;

class Solution {
    static int result = 0;
    public String solution(String number, int k) {

        boolean[] visited = new boolean[number.length()];

        combination(number, visited, 0, k, number.length());
        return Integer.toString(result);
    }

    static void combination(String number, boolean[] visited, int depth, int r, int n) {
        if (r == 0) {
            getMaxValue(number, visited);
            return;
        }

        if (depth == n) return;

        visited[depth] = true;
        combination(number, visited, depth + 1, r - 1, n);

        visited[depth] = false;
        combination(number, visited, depth + 1, r, n);
    }
    static void getMaxValue(String number, boolean[] visited) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < number.length(); i++) {
            if (!visited[i]) {
                sb.append(number.charAt(i));
            }
        }
        result = Math.max(result, Integer.parseInt(sb.toString()));
    }
}

두 번째 접근 방식은 스택을 이용하는 것이다.
number를 순회하면서 스택이 비어있거나 top이 현재 값 이하이면 스택에 삽입을 하고 현재 값보다 크다면 top보다 이하가 될 때까지 pop 시킨다. 여기서 pop을 할 땐 k를 감소시켜준다.

"4177252841"의 예시

1. 처음인 4를 넣음
stack [4] (k = 4)
2. 1은 4보다 작기 때문에 1을 넣음
stack [4, 1] (k = 4)
3. 7은 1보다 크기 때문에 1을 빼줌
stack [4] (k = 3)
4. 7은 4보다 크기 때문에 4를 빼줌
stack [] (k = 2)
5. stack이 비었기 때문에 7을 넣음
stack [7] (k = 2)
6. 위 방법을 따르면 7, 2를 넣을 수 있음
stack [7, 7, 2] (k = 2)
7. 5는 2보다 크기 때문에 2를 빼고 5를 넣음
stack [7, 7, 5] (k = 1)
8. 2는 5보다 작기 때문에 2를 넣음
stack [7, 7, 5, 2] (k = 1)
8. 8은 2보다 크기 때문에 2를 빼고 8을 넣음
stack [7, 7, 5, 8] (k = 0)
9. k가 0이기 때문에 나머지 수를 다 넣어줌
stack [7, 7, 5, 8, 4, 1] (k = 0)

📍 주의
number가 같은 숫자가 나오거나 내림차순으로 정렬이 되었을 때는 k의 원소만큼 pop시켜줘야 함‼️

나는 StringBuilder를 스택처럼 활용해서 문제를 해결했다.

💻 코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        for (char c : number.toCharArray()) {
            while(answer.length() != 0 && answer.charAt(answer.length() - 1) < c && k-- > 0) {
                answer.deleteCharAt(answer.length() - 1);
            }
            answer.append(c);
        }
        while (k-- > 0) {
            answer.deleteCharAt(answer.length() - 1);
        }
        return answer.toString();
    }
}