코딩테스트 연습탐욕법 > 큰 수 만들기 - JAVA (Stack)

 

 

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

프로그래머스

 

 

풀이 - 나의 생각

처음에는

 

조합을 사용해야 하나 했지만

 

주어지는 number의 길이가 2자리 이상, 1,000,000자리 이하이기 때문에

 

다른 방법을 생각해야 했습니다.

 

 

 

 

 

코드

Stack 활용 ver

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

 

범위 탐색 ver

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int start = 0, end = k, maxIndex = 0, max = 0, flag = 0;
        String[] nums = number.split("");
        flag = nums.length - k;
        while(answer.length() < flag){
            max = -1;
            for(int i = start; i <= end; i++){
                int num = Integer.parseInt(nums[i]);
                if(max < num){
                    max = num;
                    maxIndex = i;
                    if(num == 9) break;
                }
            }
            
            k -= (maxIndex - start);
            if(k == 0){
                answer+=number.substring(maxIndex, number.length());
                break;
            }
            start = maxIndex+1;
            answer+=nums[maxIndex];
            end++;
        }
        
        return answer;
    }
}

 

 

 

 

 

다음에 또 봐요