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

 

문제 설명

 

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

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

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

 

제한 조건

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

 

입출력 예

 

 

풀이 방법

 

문자열을 연결할 때 StringBuilder를 쓰면 시간복잡도를 줄일 수 있기에 이를 활용하기로 한다.

구하려는 숫자의 길이는 number.length-k이므로 이 길이만큼 반복하면서

최댓값이 발견된다면 이를 max로 설정하고, 그 다음에 탐색할때는 최댓값이 발견된 인덱스의

다음부터 탐색하도록 한다.

 

작성 코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution {         public String solution(String number, int k) {             StringBuilder answer = new StringBuilder();             int index=0;                          for(int i=0;i<number.length()-k;i++){ // 구하려는 코드의 길이를 먼저 설정                 char max='0';                 for(int j=index;j<=i+k;j++){                     if(max<number.charAt(j)){                         max=number.charAt(j);                         index=j+1;                     }                 }                 answer.append(max);             }                            return answer.toString();         }     }