[프로그래머스] 큰 수 만들기

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

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

2021-08-02

---

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        int[] num = new int[number.length()];
        for(int i = 0; i < number.length(); i++) num[i] = Character.getNumericValue(number.charAt(i));
        StringBuilder answer = new StringBuilder();
        int len = number.length() - k;
        int idx = -1;
        while(true) {
            int max = -987654321;
            boolean flag = false;
            for(int j = idx+1; j <= number.length()-len; j++) {
                if(max < num[j]) {
                    flag = true;
                    max = num[j];
                    idx = j;
                }
            }
            if(flag) answer.append(max);
            len--;
            if(!flag || len == 0) {
                for(int p = idx+1; p < idx+1+len; p++) {
                    answer.append(num[p]);
                }
                break;
            }
        }
        return answer.toString();
    }
}

#문제풀이

힌트를 살짝 얻어서 풀었다. 현재 기준에서 k만큼을 빼고 하나 뽑을 수 있다고 가정하고 푼 방식이다. 

기준 범위내에서 가장 큰 수를 뽑고, 뽑은 수의 다음 index 부터 length-남은k만큼까지에서 또 가장 큰 수를 뽑는 것을 반복하면 된다.

 

 

 

---

 

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

막연하게 스택으로도 되겠지, 생각하고 말았는데 푼 사람이 있어서 참고 하여 풀어봤다.