POJに挑戦 - そして挫折...
2007/08/25
java
poj
このブログの傾向として、たいがい何かにチャレンジして挫折していますね。
しかし、千里の道も一歩から。失敗して立ち上がっていきたい今日この頃です。
POJにチャレンジしてみました。
Short Codingという本を購入して紹介されていたのがPOJでした。
参考：
POJは北京大学の、プログラミングの問題を解いて競うシステムですね。
プロブレム1002に挑戦していろいろ勉強になったので、メモしておきます。
使用して言語は、javaです。
問題は、1002 -- 487-3279です。
この1002ですが、なんとなくできたので、POJでサブミットしたのですが、Time Limit Exceedがでて、失敗。で、この、Time Limit Exceedですが、時間超過というのはわかるのですが、なんでこれがでるのかが、わかってなくて、結構な時間を無駄にしてしまいました。
システムがプログラムにあたえるInputの値を標準入力で処理しないといけないのですが、これをずーとプログラムのほうでブロックして、待ちの状態になっているというふうにまちがって考えていました。
これは、制限時間内に処理ができなかったのは、プログラムのロジックが時間がかかるものであったということだったんですね。Orz...
たとえば、最初に自分がサブミットしたコードは、こんな感じでした。
s = s.replaceAll("-", "").replaceAll("(A|B|C)", "2").replaceAll(
"(D|E|F)", "3").replaceAll("(G|H|I)", "4").replaceAll(
"(J|K|L)", "5").replaceAll("(M|N|O)", "6").replaceAll(
"(P|R|S)", "7").replaceAll("(T|U|V)", "8").replaceAll(
"(W|X|Y)", "9");
"(D|E|F)", "3").replaceAll("(G|H|I)", "4").replaceAll(
"(J|K|L)", "5").replaceAll("(M|N|O)", "6").replaceAll(
"(P|R|S)", "7").replaceAll("(T|U|V)", "8").replaceAll(
"(W|X|Y)", "9");
文字列をreplaceAllの繰り返しで処理。
しかし、この処理する単位が何万（最大100,000）となればたしかに重くはなるか...
根本的に自分が書いたロジックが重たいということに気がつかず、検討違いのところをずーと調べていたりしたのでした。
で、耐えきれず、Short Codingの本を開きますと1002が紹介されていたので、コードを拝見。
C言語でしたが、ほう、ここまで、やるかという感じだった。かなり自分の試みが恥ずかしくなってしまいました。
参考にしつつ、短いコードを目指しているわけではないので、CのコードをJavaにそのままうつすすのもかっこわるいしなぁと思いながら、だらだらと、サブミットしていて、やはりだめ....
自分で考えるのを放棄して、java風のコードを探しみました。
プロブレム1002のディスカッションのページでjavaのコードをアップしている人がいました。
Detail of message
えーと、なるほどなぁ、うーん、これっなんと言う整列の仕方なんだろう？
自分の、右、左にふっていくんだよね。
いろいろを参考にして作成したのが下記のコード。
一応、Acceptされました。
package p1002;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
char[] table =
// A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,
{ '2', '2', '2', '3', '3', '3', '4', '4', '4', '5', '5', '5', '6', '6',
'6',
// P, ,R,S,T,U,V,W,X,Y
'7', '7', '7', '7', '8', '8', '8', '9', '9', '9' };
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
int c = Integer.parseInt(reader.readLine());
PhoneDictionary root = null;
do {
c--;
String s = reader.readLine();
int len = s.length();
StringBuilder b = new StringBuilder();
for (int i = 0; i < len; i++) {
char cc = s.charAt(i);
if (cc == '-')
continue;
if ('0' <= cc && cc <= '9') {
b.append(cc);
continue;
}
if ('A' <= cc && cc <= 'Z') {
int d = cc - 'A';
b.append(table[d]);
continue;
}
}
s = new String(b);
if (7 != s.length())
continue;
if (root == null) {
root = new PhoneDictionary(s);
continue;
}
root.add(new PhoneDictionary(s));
} while (c != 0);
if (root != null)
root.print();
if (PhoneDictionary.isNoduplicate)
System.out.println("No duplicates.");
}
static class PhoneDictionary {
int times = 1;;
String number;
PhoneDictionary r, l;
static boolean isNoduplicate = true;
public PhoneDictionary(String number) {
this.number = number;
}
public void add(PhoneDictionary phone) {
int i = number.compareTo(phone.number);
if (i == 0) {
times++;
} else if (i > 0) {
if (r != null) {
r.add(phone);
} else {
r = phone;
}
} else if (i < 0) {
if (l != null) {
l.add(phone);
} else {
l = phone;
}
}
}
public void print() {
if (r != null) {
r.print();
}
if (1 < times) {
isNoduplicate = false;
System.out.println(this);
}
if (l != null) {
l.print();
}
}
public String toString() {
return number.substring(0, 3) + "-" + number.substring(3) + " "
+ times;
}
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
char[] table =
// A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,
{ '2', '2', '2', '3', '3', '3', '4', '4', '4', '5', '5', '5', '6', '6',
'6',
// P, ,R,S,T,U,V,W,X,Y
'7', '7', '7', '7', '8', '8', '8', '9', '9', '9' };
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
int c = Integer.parseInt(reader.readLine());
PhoneDictionary root = null;
do {
c--;
String s = reader.readLine();
int len = s.length();
StringBuilder b = new StringBuilder();
for (int i = 0; i < len; i++) {
char cc = s.charAt(i);
if (cc == '-')
continue;
if ('0' <= cc && cc <= '9') {
b.append(cc);
continue;
}
if ('A' <= cc && cc <= 'Z') {
int d = cc - 'A';
b.append(table[d]);
continue;
}
}
s = new String(b);
if (7 != s.length())
continue;
if (root == null) {
root = new PhoneDictionary(s);
continue;
}
root.add(new PhoneDictionary(s));
} while (c != 0);
if (root != null)
root.print();
if (PhoneDictionary.isNoduplicate)
System.out.println("No duplicates.");
}
static class PhoneDictionary {
int times = 1;;
String number;
PhoneDictionary r, l;
static boolean isNoduplicate = true;
public PhoneDictionary(String number) {
this.number = number;
}
public void add(PhoneDictionary phone) {
int i = number.compareTo(phone.number);
if (i == 0) {
times++;
} else if (i > 0) {
if (r != null) {
r.add(phone);
} else {
r = phone;
}
} else if (i < 0) {
if (l != null) {
l.add(phone);
} else {
l = phone;
}
}
}
public void print() {
if (r != null) {
r.print();
}
if (1 < times) {
isNoduplicate = false;
System.out.println(this);
}
if (l != null) {
l.print();
}
}
public String toString() {
return number.substring(0, 3) + "-" + number.substring(3) + " "
+ times;
}
}
}
: