algorithms
software expert
소프트웨어 익스퍼트 1244 (software expert 1244)
·
소프트웨어 익스퍼트 1244 (software expert 1244)
소프트웨어 익스퍼트 1244
코드
import java.io.*;
import java.util.ArrayList;
public class SWE1244 {
static int t, T, ex, a[], max, b[], c[];
static String ins[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
t = T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while (T-- != 0) {
ins = br.readLine().split(" ");
a = new int[ins[0].length()];max = 0;
b = new int[ins[0].length()];
for (int i = 0; i < ins[0].length(); i++) {
b[i] = a[i] = ins[0].charAt(i) - 48;
}
ins[1] = ins[1].replace("\t", "");
ex = Integer.parseInt(ins[1]);
dfs(0, a, 0);
sb.append("#");sb.append(t - T);sb.append(" ");
sb.append(max);sb.append("\n");
}
bw.write(sb.toString());
bw.flush();bw.close();
}
private static void dfs(int idx, int[] a, int c) {
int l = a.length;
if (c == ex) {
int ans = 0;
for (int i = 0; i < l; i++) {
ans += a[i] * Math.pow(10,l - i - 1);
}
max = Math.max(max, ans);
return;
}
int chIdx = -1;
if (idx < l) chIdx = getIndexOfMax(a, idx);
if (chIdx == -1) {
if (idx == l - 1) {
int b[] = new int[10];
boolean flag = false;
for (int i = 0; i < l; i++) b[a[i]]++;
for (int i = 0; i < 10; i++) {
if (b[i] > 1) flag = true;
}
if (flag) dfs(idx, a, c + 1);
else {
swap(idx, idx - 1, a);
dfs(idx, a, c + 1);
swap(idx, idx - 1, a);
}
}else dfs(idx + 1, a, c);
}
else {
swap(idx, chIdx, a);
dfs(idx + 1, a, c + 1);
swap(idx, chIdx, a);
}
}
private static int getIndexOfMax(int a[], int s) {
int max = a[s], lastIndex = -1;
int count = 0, firstIndex = -1;
ArrayList<Integer> indices = new ArrayList<>();
for (int i = s + 1; i < a.length; i++) {
max = Math.max(max, a[i]);
}
for (int i = s + 1; i < a.length; i++) {
if (max == a[i]) {
lastIndex = i;
indices.add(i);
}
if (firstIndex == -1 && max == a[i]) firstIndex = i;
}
for (int i = s + 1; i < lastIndex; i++) {
if (a[s] > a[i]) count++;
}
return (indices.size() <= count) ? firstIndex :
indices.get(indices.size() - count - 1);
}
private static void swap(int x, int y, int[] a) {
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
}