[プログラマー]#77886110移動

質問する

0と1からなる文字列xの場合は、以下の操作でxをできるだけ早く到着させます.

xの「110」を抜き、任意の位置に挿入します.

例えば、x＝「11100」の場合、中間から「110」が抽出されると、x＝「10」となる.選択した「110」をxの前面に再挿入すると、x=「11010」になります.
変形する文字列xを複数含む文字列配列sを指定すると、solution関数を完了し、各文字列を上の動作に変換して、辞書順に一番前の文字列を配列に入れて返します.

せいげんじょうけん

1≦sの長さ≦1000000

1≦sの各元素長≦1000000

1≦sの全元素長の和≦1000000

にゅうしゅつりょく

sresult["1110","100111100","0111111010"]["1101","100110110","0110110111"]

I/O例

下図は、「1110」を「1101」にする手順を示している.

下図は、「100111100」を「100110110」にする手順を示しています.

に答える

この問題は特殊なアルゴリズムを用いて解決するというより,どのような方法で問題を解決するかである.

import java.util.Stack;

class Solution {
    public String[] solution(String[] s) {
        String[] answer = new String[s.length];
        StringBuilder sb;
        
        for(int i=0; i<s.length; i++) {
            String str = s[i];
            Stack<Character> stack = new Stack<>();
            int cnt = 0;
            
            for(int j=0; j<str.length(); j++) { 
                char z = str.charAt(j);
                
                if(stack.size()>=2) {       //110을 계속해서 뽑아줌, 먼제 110을 다 뽑아놓으면 어떻게 배치를 해도 110 더 나오진 않음
                    char y = stack.pop();
                    char x = stack.pop();
                    
                    if(x=='1' && y=='1' && z=='0') {
                        cnt++;
                        continue;
                	}
                    
                    else {
                        stack.push(x);
                        stack.push(y);
                        stack.push(z);
                    }
                }
                
                else
                    stack.push(z);
            }
            
            int idx = stack.size();
            boolean flag = false;
            sb = new StringBuilder();
            
            while(!stack.isEmpty()) {           //남은 문자열 중에서 제일 마지막 글자부터 1이 이어지는 부분 idx을 찾음
                if(!flag && stack.peek()=='1')
                    idx--;
                if(!flag && stack.peek()=='0')
                    flag = true;
                sb.insert(0, stack.pop());
            }
           
            if(cnt>0) {
                while(cnt>0) {
                    sb.insert(idx, "110");    //1이 존재하면 idx에 110을 갯수만큼 추가하고 0이 아예 없다면 문자열 끝에 추가
                    idx += 3;
                	cnt--;
            	}
                
                
                answer[i] = sb.toString();
            }
            
            else
                answer[i] = s[i];           //110이 존재하지 않다면 문자열은 변하지 
        }
        
        return answer;
    }
}