[프로그래머스 고득점 kit]탐욕법 Level2 큰 수 만들기

문제 설명

 

어떤 숫자에서 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

 

접근 방법

입력된 number에서 k개의 수를 빼서 만들 수 있는 가장 큰 수를 구하는 문제이다. 

 

number에서 어떻게하면 k개의 수를 뺀 것 중에 가장 큰 수가 될 수 있는지 고민해보아야 한다.

 

다양한 방법들이 존재하겠지만 나는 number중 가장 앞에서 부터 k+1개의 후보군을 만들어 그 중 가장 큰 수를 선택하여 answer에 이어붙였다.

 

예를 들면, number=1231234, k=3 일 때 1231이 가장 큰 수를 뽑을 후보군이 되는 것이다. 이중 가장 큰 수는 3이다. 3을 선택하면 3보다 앞에 있는 숫자 1, 2는 버려진다. 1, 2가 버려지면 이제 빼야할 숫자는 1개가 남게된다(3-2=1).  

 

1과 2는 버려지고 3은 선택되었기 때문에 1, 2, 3은 제외 되어야하기 때문에 number는 1234, k는 1이 되고 위 과정을 다시 반복하면 된다. 그리고 k가 0이 되면 number의 남은 수를 모두 이어 붙인다.

 

 

여기까지만 생각하고 소스코드를 작성하면 런타임 오류가 발생한다. 소스 코드에서 런타임 오류가 발생할 부분을 생각 해보면 문자열의 인덱스 부분 밖에 존재하지 않는다.

 

 따라서 나는 테스트 케이스를 고민 해보았고 number=54321, k=1인 경우 에러가 발생하는 것을 알게되었다. 이 경우 끝까지 k가 감소하지 않아 반복문 내부로 들어오면 인덱스 에러가 발생하게 된다. 따라서 answer의 길이가 number 길이 - k 가 되면 반복문을 종료하는 조건을 만들어야 한다.

 

소스 코드

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        String subNumber = number;
        int returnLen = number.length() - k;
        
        while(k > 0 && answer.length() != returnLen){
            String temp = subNumber.substring(0, k+1);
            int idx = 0;
            char max = temp.charAt(0);
            for(int i=1;i<temp.length();i++){
                if(max < temp.charAt(i)){
                    max = temp.charAt(i);
                    idx = i;
                }
            }
            
            k -= idx;
            answer += max;
            if(subNumber.length() >= idx+1)
                subNumber = subNumber.substring(idx+1);
        }
        if(answer.length() != returnLen)
            answer += subNumber;
        return answer;
    }
}

 

그리고 동일한 메커니즘이지만 Stack을 사용한 훨씬 더 나은 소스코드가 있었다.

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);
    }
}

 

 

느낀점

이번 글을 쓰면서 내 생각을 정리하지 않고 작성하다보니 장황해졌다. 생각을 정리하고 작성할 필요가 있을 것 같다.

이 문제를 처음 풀 때는 40분이 걸려도 풀지 못했다. 그래서 다음날은 노트와 연필을 들고 손으로 생각을 써가며 푸니 더 잘 풀리는 것 같다. 노트와 펜을 사용하자.