|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import java.util.*;
class Solution {
public String solution(String number, int k) {
String answer = "";
int len = number.length() - k;
int start = 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
int max = -1;
for (int j = start; j <= i + k; j++) {
int n = number.charAt(j) - '0';
if (max < n) {
max = n;
start = j + 1;
}
}
sb.append(max);
}
answer = sb.toString();
return answer;
}
}
|
cs |
최대 k개의 수를 제거하여 가장 큰 수를 만드는 알고리즘이다.
k개의 수를 제거한다는 것은 length - k개를 고르는 것과 같다.
선택할 수 있는 최대 범위는 i + k인데, 기본적으로 k개를 제거하기 때문에 인덱스 k까지 확인할 수 있는 것이다.
이 와중에 선택을 1개씩 하기 때문에 i가 추가로 더해진다.
선택을 시작하는 구간은 고정되지 않아서, 이전에 선택한 가장 큰 값이 있던 인덱스 + 1부터 시작한다.
모든 경우의 수를 이용하여 구했지만, 메모리 및 시간 초과로 실패한 코드는 아래와 같다.
소수 찾기 문제에서 다른 사람이 작성했던 permutation 함수를 변형하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import java.util.*;
class Solution {
public void permutation(String str, int len, HashSet<String> set){
int n = str.length();
if (n == len) {
set.add(str);
return;
}
for (int i = 0; i < n; i++)
permutation(str.substring(0, i) + str.substring(i + 1, n), len, set);
}
public String solution(String number, int k) {
String answer = "";
HashSet<String> set = new HashSet<>();
int len = number.length() - k;
String answer = "";
permutation(number, len, set);
answer = Collections.max(set);
return answer;
}
}
|
cs |