読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Best Cow Line(PKU No.3617)

Best Cow Line(PKU No.3617)

N文字の文字列Sが与えられ、N文字の文字列Tを作る。はじめはTは長さ0の文字列で、次のいずれかの操作が行える。
・Sの先頭を1文字削除し、Tの末尾に追加する。
・Sの末尾を1文字削除し、Tの末尾に追加する。
辞書順比較でできるだけ小さくなるようにTを作る。
※PKU No.3617では、80文字ごとに改行するという指示がある。
制約
1 \leq N \leq 2000
文字列Sに含まれるのはローマ字の大文字のみ

アルゴリズム

Sの両端を比較して、小さいほうをグリーディにTの末尾していく。
ただし、Sの両端が同じ文字のとき、注意が必要。反転した文字列S’とSを比較して、Sが小さいならSの先頭を、そうでないならSの末尾をTに追加しなければならない。

コード

C++ならreverseを使うか、string(s.rbegin(),s.rend())を使えばおk

import java.util.*;
import java.lang.*;
public class pku3617 {
	static Scanner scanner;
	
	pku3617(){
		int N = scanner.nextInt();
		String str = "";
		for(int i=0; i<N; i++) str += scanner.next();
		solve(N,str);
	}
	
	void solve(int N, String str){
		 int count = 0; //pku3617に、80文字ごとに改行という指示があった
		StringBuilder s = new StringBuilder(str);
		while( s.length() > 0 ){
			char top = s.charAt(0);
			char last = s.charAt( s.length()-1 );
			if( top < last ){
				s.deleteCharAt(0);
				System.out.print( top );
			}else if( top > last ){
				s.deleteCharAt( s.length()-1 );
				System.out.print( last );
			}else{
				String S = s.toString();
				String RS = s.reverse().toString();
				if( S.compareToIgnoreCase(RS) < 0 ) s.deleteCharAt( s.length()-1 );
				else s.deleteCharAt(0);
				System.out.print( top );
			}
			if( ++count == 80 ){
				System.out.println("");
				count = 0;
			}
		}
	}
	
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new pku3617();
	}
}