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

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

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

 

• 주어진 String에서 큰 수를 조합하는건줄 알았는데 그냥 순서 그대로 놓고 제거만해서 가장 큰 수를 만드는 것이었다.

 

 

 

• 2개씩 비교하여 작은 수를 삭제하는 방식

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        
        StringBuilder sb = new StringBuilder(number); // number 문자열 삭제가 용이하기위해 사용
        int index = 1;
        int delCount = 0;
        
        while(delCount != k) { // k개 제거할때까지
            if(index >= 1 && sb.charAt(index - 1) < sb.charAt(index)) { // 맨 앞에서부터 2개씩 비교해서 뒤의 숫자가 더 크면
                sb.deleteCharAt(index - 1); // charAt(index-1)의 숫자가 더 작으므로 앞의 숫자 제거
                index--; // 앞의 숫자가 제거되고 하나씩 앞당겨짐
                delCount++; // 삭제한 개수 증가
            } else { // index가 0이거나 앞의 숫자가 더 크면
                if(index == sb.length() - 1 && sb.charAt(index) <= sb.charAt(index - 1)) { // index가 끝까지가면, 그리고 그게 그 전 숫자보다 작으면
                    sb.deleteCharAt(index); // 작은 숫자를 제거
                    index--;
                    delCount++;
                } else{
                    index++;
                }
            }
        }
        
        answer = sb.toString();
        
        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);
    }
}