링크

큰 수 만들기

문제설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

풀이

처음 문제를 접근하였을 때 arraylist를 만들고 number.toCharArray를 해서 list에 다 삽입하였다.

그 후 이중for문의 안쪽 for문을 for(int i=0; i>k; i++)이런 식으로
가장 작은 값을 찾아 list의 index를 remove시켜주었다.
그 다음 삭제한 cnt가 k가 같아지면 종료를 시키게 만들어주었지만

hideen case에서 시간초과와 엄청난 빨간색 글씨들..^^
근데 number가 1,000,000자리 이상이었기에 어느정도 예상은 가능했다.

그렇게 구글링을 하니
여기도 이중 for문이었지만

접근법을 보니 number.length()-k만큼 돌린다. 이 뜻은 그냥 k값을 뺀 나머지 길이만 구한다는 뜻이다.

그 후, k+i만큼 돌린다는 것은 그렇게 해야 number.length()-k만큼 max값을 하나씩 고를 수 있기 때문! 그리고 max값을 찾는다면 max인덱스의 한칸 뒤에서부터 다시 탐색하면 된다.

Code

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb=new StringBuilder();
        int idx=0;
        
        for(int i=0; i<number.length()-k; i++)
        {
            int max=-1;
            for(int j=idx; j<=k+i; j++)
            {
                if(max < number.charAt(j)-'0')
                {
                    max=number.charAt(j)-'0';
                    idx=j+1;
                }
            }
            sb.append(max);
        }
        
        String answer=sb.toString();
        return answer;
    }
}