2639 Necklace Decomposition

「2639 Necklace Decomposition」の編集履歴（バックアップ）一覧はこちら

「2639 Necklace Decomposition」(2006/05/14 (日) 00:42:00) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2639 Necklace Decomposition
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         for(int c=0;c<n;c++){
             String line = sc.next();
             ArrayList<Integer> segs = new ArrayList<Integer>();
             segs.add(0);
             for(int i=1;i<line.length();i++){
                 if(line.charAt(i-1)=='1'&&line.charAt(i)=='0'){
                     segs.add(i);
                 }
             }
             segs.add(line.length());
             
             while(true){
                 boolean end = true;
                 
                 for(int i=0;i<segs.size()-2;i++){
                     String s1 = line.substring(segs.get(i), segs.get(i+1));
                     String s2 = line.substring(segs.get(i+1), segs.get(i+2));
                     if(isNecklace(s1.concat(s2))){
                         segs.remove(i+1);
                         end = false;
                     }
                 }
                 
                 if(end) break;
             }
             
             for(int i=0;i<segs.size()-1;i++){
                 System.out.print("("+line.substring(segs.get(i), segs.get(i+1))+")");
             }
             System.out.println();
         }
     }
     public static boolean isNecklace(String s){
         int n = s.length();
         for(int i=1;i<n;i++){
             String s1 = rotate(s, i);
             if(s.compareTo(s1)>0) return false;
         }
         return true;
     }
     public static String rotate(String s, int d){
         char[] ret = new char[s.length()];
         for(int i=0;i<s.length();i++){
             ret[i] = s.charAt((i+d)%s.length());
         }
         return new String(ret);
     }
 }