[프로그래머스 (Java)] 큰 수 만들기

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

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

Greedy 알고리즘은 부분적인 최적해를 계속 확장 시켜서 전제적인 최적해를 찾는 알고리즘 입니다.

이 문제에서 쟁점은 크게 세가지 입니다.

1. 부분적인 최적해가 전체적인 최적해가 될 수 있는가
2. 부분적인 최적해를 어떻게 구할 것인가
3. 부분적인 최적해를 구할때 시간복잡도 최소화

1. 부분적인 최적해 정의

전형적인 Greedy 문제로서 난이도는 평이한것 같습니다.

우선 부분적인 최적해를 어떻게 설정해야지 전체적인 최적해가 될 수 있을지에 대해 생각해보면, 

k = 1, 2, 3, 4, .... 처럼 제거하는 숫자의 개수를 증가시켜 가는 방식으로 부분해를 정의할 수 있을 것 같습니다

즉 숫자 m 개를 제거했을때 가장 큰 숫자를 구했을때, 추가적으로 1개를 잘 제거하면 m + 1 개를 제거했을때 가장 큰 숫자를 구할 수 있다 가 본문제이 Greedy 로서의 핵심입니다.

위와 같은 사실을 확인하면 문제를 다음과 같이 단순화 할 수 있습니다.

n 개의 숫자를 제거해서 가장 큰 숫자를 만들어라 → 1개의 숫자를 제거해서 가장 큰 숫자를 만드는 과정을 n 번 반복해라

 

2. 부분적인 최적해를 어떻게 구할 것인가

그럼 어떤 기준으로 숫자 한개를 제거해서 가장 큰 숫자를 만들것 인가 에 대해서 생각해 보겠습니다.

숫자 4789 를 생각해보면 당연히 4를 제거할 것입니다. 그럼 7489 의 경우는 어떤가요? 4를 제거할 것입니다.

즉 앞에서부터 숫자를 하나씩 확인해 나갈때, 확인중인 숫자 A의 크기가 바로 뒤에 오는 숫자 B보다 작은경우 확인중인 숫자 A를 제거하게 됩니다.

4789 의 경우는 4 < 7 이기 때문에, 7489 의 경우 7 > 4 이고 4 < 8 이기 때문에 각각 4를 제거해야 가장 큰 숫자를 만들 수 있습니다.

수식으로도 쉽게 증명할 수 있는데 n 자리의 숫자의 경우 각 자리 수를 의미하는 a_1 ~ a_n 수열을 정의하고

처음으로 a_m < a_m+1 인 숫자 m 이 있을때 a_m 이 아니라 다른 숫자를 제거한 경우와 비교하면 a_m 을 제거하는게 최댓값이 된다는 것을 확인할 수 있습니다.

 

만약 모든 수가 자신의 뒷자리 숫자보다 크거나 같다면 가장 뒷자리 숫자를 제거하는게 제일 큰 수를 얻을 수 있는 방법입니다.

987654321 에서 5개를 제거해야한다고 생각하면 쉽게 이해할 수 있습니다.

 

3. 부분적인 최적해를 구할때 시간복잡도의 최소화

Greedy 의 예시 문제임에도 Stack 을 생각하지 못하면 풀 수 없는 문제입니다. 저도 컴퓨터 공학 전공이 아니라 이 부분에서 몇십분은 소요된거 같습니다. 숫자를 하나씩 꺼내서 Stack 에 넣으면서, 이미 들어가 있는 숫자중에 가장 위에 있는 수 (즉 가장 최근에 stack 에 들어간 숫자) 와 현재 넣으려고 후보에 둔 숫자를 비교하면서, 만약 지금 숫자가 Stack 의 최상단에 있는 숫자보다 크고 제거가능한 횟수 (k) 가 충분하다면 넣으려는 숫자보다 큰 숫자가 나올때까지 stack 에서 숫자를 제거하고, 제거한 횟수만큼 k 값을 차감합니다.

만약 k 값을 다 사용하기 전에 모든 숫자에 대한 검사가 끝난다면, stack 에 들어가 있는 수는 앞에서 부터 nondecreasing sequence 를 이루고 있기때문에 가장 나중에 넣은 숫자를 남은 k 만큼 제거해주고, stack 에 남은 문자로 answer 을 작성해줍니다.

 

import java.util.Stack;

class Solution {
    public String solution(String number, int k) {
        Stack<Character> numberStack = new Stack<>();
        char[] numberArray = number.toCharArray();
        for (int i = 0; i < numberArray.length; i++) {
            while (!numberStack.isEmpty() && k != 0 && numberStack.peek() < numberArray[i]) {
                numberStack.pop();
                k--;
            }
            numberStack.push(numberArray[i]);
        }
        while (k != 0) {
            numberStack.pop();
            k--;
        }

        StringBuilder sb = new StringBuilder();
        while (!numberStack.isEmpty()) {
            sb.append(numberStack.pop());
        }
        String answer = sb.reverse().toString();
        return answer;
    }
}