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

 

 

문제 링크

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

프로그래머스

 

 

문제 풀이

1. 숫자로 이루어진 문자열 number에서 k개의 숫자를 제거하여 가장 큰 숫자를 문자열 형태로 return한다.

2. number는 2자리 이상, 1,000,000의 수로 시간복잡도 O(N²)의 알고리즘은 사용할 수 없다.

 

 

 

코드1 _index를 이용한 방법

index+k번째까지 체크하여 index의 숫자보다 큰 숫자가 있으면 index번째 숫자는 삭제한다.

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();
        int len=number.length();
        for(int i=0; i<len;i++){
            char cur = number.charAt(i);
            boolean isRemoveNumber = false;
            for(int j=1; j<=k;j++){
                if(j+i >= len) break;
                if(cur<number.charAt(i+j)){
                    isRemoveNumber = true;
                    k--;
                    break;
                }
            }
            if(!isRemoveNumber) sb.append(cur);
        }
        String result = sb.toString();
        return result.substring(0,result.length()-k);
    }
}

 

 

 

실행 결과1

 

 

---

 

코드2_Stack을 이용한 방법

stack을 이용하여 i번째 수보다 큰 수가 나올때까지 pop()

import java.util.Stack;
class Solution {
    public String solution(String number, int k) {
        Stack<Character> stack = new Stack();
        for(char c : number.toCharArray()){
            while(!stack.isEmpty() && stack.peek()<c && k>0){
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<k;i++) stack.pop();
        while(!stack.isEmpty()) sb.append(stack.pop());
        sb.reverse();
        return sb.toString();
    }
}

 

 

 

실행 결과2