Programmers - 큰 수 만들기 with JAVA (V)

 

문제

문제는 굉장히 간단하다. 주어진 숫자에서 순서를 바꾸지 않고 K만큼의 수를 삭제하여 가장 큰수를 만드는 것이다.

예를들어, 18403, k=2일때, 843이 되는 것이다.

 

 

 

아이디어 및 로직

우선적으로 아이디어는 앞에서부터 삭제할지 여부를 판단하는데 현재 값이 앞에 있는 값보다 작으면 삭제를 한다.

예를 들어, 83845가 있을 때, 8을 입력, 3을 입력, 8을 입력할 때는 3은 삭제된다.

 

1. Check 리스트 생성

2. 주어진수의 첫번째 수부터 확인

3. Check 리스트가 비어있다면 초기값 삽입 후 다음 수 확인

4. 현재 수가 Check리스트의 마지막 수보다 크다면 현재 수보다 작은 Check리스트 안의 수 모두 삭제 K -= 1

(가장 최근값(전의 값)이 현재 수보다 작다면 삭제 -> 만약 크다면 다른수도 큰거라서 멈출 수 있다.)

5. 3-4번의 경우가 없다면 그냥 삽입

 

 

 

코드

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        char[] check = number.toCharArray();
        List<Integer> values = new ArrayList<>();
        values.add((int)(check[0]-48));
        for(int i=1; i<check.length; i++){
            int now = (int)(check[i]-48);
            while(values.size()>0 && values.get(values.size()-1)<now && k >0){
                k -= 1;
                values.remove(values.size()-1);
            }
            values.add(now);
        }
        for(int i=0; i<k; i++){
            values.remove(values.size()-1);
        }
        StringBuilder sb = new StringBuilder();
        for(int value : values){
            sb.append((char)(value+'0'));
        }
        return sb.toString();
    }
}