큰 수 만들기

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

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

 

문제 설명

어떤 숫자에서 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. 문자열로 들어온 숫자를 하나씩 꺼내며 스택에 넣는다. 
2. 이때 스택의 마지막 요소보다 다음요소가 크면 스택의 마지막 요소를 제거(pop)해주고 k의 값을 1씩감소시킨다.
3. pop할 때 주의할 점은 다음요소보다 stack의 마지막 요소가 크다면 pop을 멈추는 것이다.
4. pop여부와 상관없이 다음요소를 넣어(push)준다.

위와 같은 설계로 코드1을 짰더니 런타임이 나오는데;; 질문하기 올라온 테케들을 모두 넣어보면 잘된다..;;
그래서 다른 사람 풀이를 찾다보니 대부분 for문을 중첩해서 썼는데, 우연히 나와같이 스택으로 접근한분의 코드를 참조했다.
코드2를 보니 큰 틀에서는 나와 결이 같지만 코드가 간결하고 우아하다...
설계방향은 같은걸 봐서는 코드1은 휴먼에러인듯 싶다... 아직은 못찾았다.

코드1(실패 - 테스트케이스 2 ~ 10 런타임)

import java.util.*;
// number에 들어온 숫자를 하나씩 꺼낸다 
// 이전 숫자랑 비교했을 때
// pop을 해준다. 
// (앞의 요소가 큰경우에는 break, k == 0이면 탈출)
class Solution {
    public String solution(String number, int k) {
        
        if ( number.length() == 1 ) return number;
        
        Stack<Integer> stack = new Stack<>(); 
        
        for ( int i = 1; i < number.length(); ++i ) {
            
            int beforeNum = Integer.parseInt( String.valueOf(number.charAt( i - 1 )) );
            int afterNum  = Integer.parseInt( String.valueOf(number.charAt( i )) );
            
            // 최초 숫자는 넣어준다.
            if ( i == 1 ) {
                stack.push( beforeNum );
            }
            
            // 이전 숫자보다 다음 숫자가 큰경우 이전숫자를 지운다.
            if ( beforeNum < afterNum ) {
                out : while ( !stack.isEmpty() && k > 0 ) {
                    int lastNum = stack.peek();
                    if ( afterNum < lastNum ) break out;
                    stack.pop();
                    --k;
                }   
            } 
            // 이전 숫자가 다음 숫자랑 같거나 큰경우 계속 넣어준다.
            stack.push( afterNum );  
             
        }
        
        // stack에 숫자가 있으며, k가 남아있는 경우 숫자를 제거해준다.
        // (999, 2) 같은 경우 9가 답이되어야하므로.
        while ( !stack.isEmpty() && k > 0 ) {
            stack.pop();
            --k;
        }
        
        // 문자열로 이어붙인다.
        StringBuilder answer = new StringBuilder();
        for ( int num : stack ) {
            answer.append(num); 
        }
        
        // 000인 경우 0으로 처리해주기위해 한번 파싱한다.
        int tmp = Integer.parseInt( answer.toString() );
        
        // 답을 반환한다.
        return (tmp == 0) ? "0" : (tmp + "");
    }
}

 

코드2(성공)

import java.util.*;
 
 
class Solution {
    public String solution(String number, int k) {
        
        int len = number.length();
        char[] answer = new char[len - k];
        Stack<Character> stack = new Stack<>();
        
        for ( int i = 0; i < len; ++i ) {
            char num = number.charAt( i );
            while ( !stack.isEmpty() && stack.peek() < num && k-->0 ) {
                stack.pop();
            }
            stack.push( num );
        }
        
        for ( int i = 0; i < answer.length; ++i ) {
            answer[i] = stack.get(i);
        }
        
        return new String( answer );
    }
}