[PG] 큰 수 만들기 JAVA

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

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

숫자형 문자로 이뤄진 String number 과 int k가 주어진다.

number 에서 숫자를 k개 제거했을 때 나올 수 있는 수의 최대값을 String으로 반환해야한다.

(단, number 안에서 유지되는 숫자들의 순서가 바뀌면 안 된다. number의 수들로 가장 큰 조합을 찾아내는 게 아니라는 뜻)

 

 

 

풀이 1.

class Solution {
    public String solution(String number, int k) {
        // StringBuilder 안 쓰면 시간초과
        StringBuilder sb = new StringBuilder();

        // j의 범위에 1씩 증가하는 i를 더하는 이유는 뽑아야 하는 숫자가 number.length()-k개에서 하나씩 줄어들기 때문
        // 예를들어 length : 7, k : 3 이라면 새로 뽑아야 하는 수는 총 4개
        // 즉, 늦어도 [k] 에서는 첫번째 수를 뽑아야 하나는 것
        // 이는 다시말하면 뒤에서부터 3개(length - k - 1)는 남겨놓고 나머지 범위에서 하나를 뽑아야 한다는 것
        // 숫자를 하나씩 뽑을 때마다 뒤에 남겨놔야 하는 수의 개수도 하나씩 줄어든다.
        // 그래서 1씩 증가하는 i를 더해준다

        int next = 0;
        for(int i = 0; i < number.length() - k; i++) {
            char max = '0';
            for(int j = next; j <= k + i; j++) {
                if(max < number.charAt(j)) {
                    max = number.charAt(j);
                    next = j + 1;  // 다음 자리수를 선택할 범위의 시작점은 이전 자리수를 선택한 바로 다음으로 잡는다
                }
            }
            sb.append(max);
        }
        return sb.toString();
    }
}

 

혼자서 답을 생각하지 못하고 다른이의 코드를 참고했다.  ( O(n^2) 의 시간 복잡도 )

 

k개의 숫자를 제거해야한다. 다시말해 number.length - k 개의 숫자를 뽑아야 한다.

 

각 자리의 숫자를 어디에서 뽑을지 범위를 특정할 수 있다.

(특정 가능한 범위에서 그때마다 가장 큰 수를 뽑으면 되기 때문에 그리디)

 

첫번째 자리수를 뽑으려면 일단 뒤에서부터 number.length - k - 1 개는 남겨두어야 한다. 그렇지 않으면 남아있는 모든 수를 다 뽑아도 number.length - k 개를 채우지 못할 수도 있기 때문.

 

이를 풀어서 다시 말하면 첫번째 자리 수는 반드시 [0] ~ [k] 에서 나와야 한다.

이 범위에서 가장 큰 수를 골라 첫번째 자리수로 삼는다.

 

두번째 자리는 첫번째 자리를 뽑은 바로 다음 인덱스부터 탐색해야한다.(int next) 이번에는 뒤에서부터 number - k - 2 개를 남겨두어야 한다. (뽑은 숫자가 늘어날 때마다 뒤에서부터 남겨둬야 하는 숫자의 개수는 줄어든다)

 

즉, i 번째 수를 뽑는 반복 for ( int i ) 를 한 번 돌 때마다 그 안에서 실질적으로 i 번째 수를 찾는 역할을 하는 for ( int j )의 범위에 +i 를 해주어야 한다.

 

다시 말하면 탐색 범위의 끝 인덱스는 [k], [k+1], [k+2] ... 이렇게 늘어난다는 이야기.

 

 

 

풀이 2.

import java.util.Stack;

class Solution {
    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();

        for (int i=0; i<number.length(); i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                stack.pop();
            }
            stack.push(c);
        }
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }
}

 

'다른 사람의 풀이' 에서 보고 배운 코드이다.  ( O(n) 의 시간 복잡도 )

 

문자열을 반복을 돌면서 전부 스택에 집어넣는다. 

이때 새로 들어오는 문자가 가장 최근에 들어온 문자보다 크다면 최근에 들어온 문자는 빼버린다.

그 후 스택에서 필요한만큼의 문자를 꺼내 반환한다.

 

O(n^2) 에서 O(n) 으로 줄어들었다.

 

대체 어떻게 이런 생각을 하는거지..?