[Java] 프로그래머스 Lv.2 > 큰 수 만들기

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

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

 

풀이

탐욕법(Greedy) 문제다.

어떤숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하기 위해서, 어떤숫자의 길이 -k번 만큼 for문을 돌려 가장 큰 숫자를 남겨 답으로 return해주었다.

정렬시간을 줄이는 방법!

1. 숫자를 비교하던 도중 9가 나오면 더이상 비교할 필요가 없으니 break 해준다.
2. k-1개까지의 숫자를 제거한 상태에서 1개의 숫자만 남았을때, 더이상 비교할 필요가 없으니 break 해준다

예를 들어 숫자 1924에서 수 두 개를 제거 한다고 하자. 그럼 첫번째로 192에서 가장 큰 수 9를 뽑는다. (이 때, 2번째에서 9가 나왔으니 2까지 비교할 필요없이 break) 그 다음 숫자인 24에서 가장 큰 수 4를 뽑는다. 따라서 결과는 94가 된다!

+ 다시돌려보니 런타임 에러가 나서 StringBuilder로 변경해주었다.

class Solution {
    public String solution(String number, int k) {
        //String answer = "";
        StringBuilder answer = new StringBuilder();
        char[] c = number.toCharArray(); // String to char Array

        int cnt=0;
        char max='0';
        for(int i=c.length-k;i>0;i--){ // c.length-k번 반복
            max=c[cnt];
            for(int j=cnt;j<=c.length-i;j++){
                if(c[j]=='9'){ cnt=j; break;} // 9일땐 더 이상 탐색할 필요없으니 break
                if(max < c[j]) { max=c[j]; cnt=j;}
            }
            answer.append(c[cnt]);
            cnt++; // 큰 숫자 넣어주고 그 다음숫자부터 반복하기위해 cnt++
            
            // 마지막숫자만 남았을 때
            if(cnt!=c.length-k && cnt==c.length-1){
                //answer+=c[cnt];
                answer.append(c[cnt]);
                break;
            }
        }
        
        return answer.toString();
    }
}

 

Stack 이용

스택을 이용했을때 시간이 훨씬 빠르고 코드도 간결함을 볼 수 있다.

위 방법과는 반대로 생각했다. k개 수를 제거한다는 것에 중점을 둬서, 스택에 마지막에 넣은 값이 현재 넣으려는 숫자와 비교했을때 더 작다면 stack에서 꺼내준다. 꺼내주는 횟수가 k번을 넘지 않을 때까지만 pop()한다.

k개의 수를 제거했다면 나머지 숫자는 그대로 stack에 push하게 되고, stack에 있는 수를 꺼내 return하기만 하면 된다.

import java.util.Stack;
class Solution {
    public String solution(String number, int k) {
        char[] answer = 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<answer.length;i++)
            answer[i] = stack.get(i);
        
        return new String(answer);
    }
}