이 남성은 열심히 개발합니다.

문제

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

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

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

제한 조건

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

나의 코드

class Solution {
    public static String solution(String number, int k) {
        String[] arr1 = number.split("");
        int[] arr = new int[arr1.length]; 
        for(int i=0; i<arr.length; i++) { arr[i] = Integer.parseInt(arr1[i]); }
        int cnt = arr.length-k;
        int left = 0;
        int right = k+1;
        StringBuilder sb = new StringBuilder();
        while(cnt>0) {
        	int max = 0;
        	for(int i=left; i<right; i++) {
        		if(arr[i]>max) {
        			max = arr[i];
        			left=i+1;
        		}
        	}
        	sb.append(max);
        	right++; cnt--;
        }
        return sb.toString();
    }
}

나의 풀이

탐욕법 알고리즘의 이름에 걸맞게 그 순간순간의 최댓값을 구해서 수를 완성시키면 된다.

테스트 케이스 10번에서 계속 시간 초과가 떠서 진짜 너무 답답했지만 number를 parsing 한 값들을 String으로 들고 int와

비교해줄 때마다 Integer.parseInt()를 사용해서 그런 것이었다. 그래서 그냥 처음부터 int[] array에 Integer.parseInt로 int로 가지고 있는다.

1. 우선 문자열 number를 parsing 하여 arr1 array에 저장한다.

2. int[] array를 선언하고 크기는 arr1.length로 해준다.

3. for문을 통해 String Array에 들어있는 값들을 int Array에 옮겨준다 ( Integer.parseInt를 통해 )

4. int cnt는 while문을 제어할 카운터 변수이다. 

5. int left 와 right는 Array의 왼쪽 index와 index가 오른쪽으로 몇 번 움직일지(right)를 판단해줄 변수이다.

6. int right의 초기값은 인자로 넘어온 k에 +1 해준 값으로 설정해준다. (arr [left]에서 right-left번 반복한다가 된다)

6. StringBuilder는 while문이 한번 돌 때마다 나오는 값을 append시켜주는데 그냥 String을 쓰는 것보다 효율적이라고 해서 사용

7. while문이 시작되면 int max를 초기화시켜준다. (max는 매 순간순간의 최댓값이 저장된다)

8. for문을 통해 left부터 right까지의 값 중에 최댓값을 if문을 통해 찾아낸다. 

9. 최댓값의 index를 찾았다면 그다음부터 탐색해야 하기 때문에 left=i+1이 된다.

10. for문이 끝나고 max가 도출되면 StringBuilder sb에 append 시켜준다.

11. right는 한 칸 늘려주고 cnt는 한번 빼준다.

12. return type이 String이기 때문에 return sb.toString()으로 마무리한다.