poj 1146 - ID Codes 2007/09/13

1146 -- ID Codes

この問題の解法が知りたい。。。

ネットでpascalでかかれたコードを読み解きながら、なんとかjavaにしてみて、ようやくサブミットできた。

書き散らしたコードだけど公開しておきます。

package p1146;

import java.io.IOException;
import java.util.Scanner;

//abaacb
//cbbaa
//a
//cab
//abcd
//acbb
//azyxwvutsrqpppooonnnmmmlllkkkjjjiiihhhgfedcccbbaaa

//ababac
//No Successor
//No Successor
//cba
//abdc
//babc
//baaaabcccdefghhhiiijjjkkklllmmmnnnooopppqrstuvwxyz
public class Main {

public static void main(String[] args) throws IOException {

Scanner scanner = new Scanner(System.in);

while (true) {
String s = scanner.next();
if ("#".equals(s))
break;
int len, i, j;
char x;
char[] line = s.toCharArray();

len = line.length;
i = len;

do {
i = i - 1;
x = line[i];
j = i - 1;
while (-1 < j && x <= line[j]) {
j = j - 1;
}
// System.err.println("j==" + j + " i==" + i + " x==" + x);
} while (!(-1 < j || i == 0));

// for (i = len - 1; 0 < i && line[i - 1] >= line[i]; i--);
//System.err.println("j==" + j + " i==" + i + " x==" + x);
if (j == -1) {
System.out.println("No Successor");
continue;
}

// String leftPart = s.substring(0, j);
// System.out.print(leftPart);
//System.out.print("[");
for (int k = 0; k < j; k++)
System.out.print(line[k]);
//System.out.print("]");
//System.out.print("[");
System.out.print(x);
//System.out.print("]");

String rightPart = omit(s, i);

System.out.print(a(rightPart.substring(j, len - 1)));
//System.err.println(rightPart);
System.out.println();

}

}

public static String a(String s1) {
char[] s = s1.toCharArray();
int i, j, min;
char x;

for (i = 0; i < s.length - 1; i++) {
min = i;
for (j = i + 1; j < s.length; j++) {
if (s[j] < s[min]) {
min = j;
}
if (min != i) {
x = s[i];
s[i] = s[min];
s[min] = x;
}

}

}

return new String(s);
}

static String omit(String s, int i) {
if (s.length() <= i)
return s;
StringBuilder builder = new StringBuilder(s);
return new String(builder.deleteCharAt(i));
}
}