110 옮기기

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.

x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.

변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ s의 길이 ≤ 1,000,000
1 ≤ s의 각 원소 길이 ≤ 1,000,000
1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000

사전순으로 가장 앞에 올수있는 110은 111보다 앞에있을뿐이므로 가장 마지막 0이 나타나거나 0이없다면 가장 앞에 모인 값을 출력하면된다.
(0이 나올수 있는 조건은 10x이거나 00x일때만이기 때문이다.)

코드(시간초과)

class Solution {
    public String[] solution(String[] s) {
        String[] answer = new String[s.length];
        int count =0;
        for(String t : s){
            StringBuilder sb = new StringBuilder();
            StringBuilder num = new StringBuilder();
            sb.append(t);
            while(true){
                int flag=0;
                if((flag=sb.indexOf("110")) != -1 ){//문제의 원인
                    
                    num.append("110");
                    sb.delete(flag,flag+3);
                    continue;
                }
                break;
            }
            int flag=0;
            if((flag=sb.lastIndexOf("0"))!=-1){
                sb.insert(flag+1,num.toString());
            }else{
                sb.insert(0,num.toString());
            }
            
            answer[count++] =sb.toString();
        }
        
        return answer;
    }
}

처음에는 indexOf로 편하게 110의 값을 찾은후 그걸 넘기는 방식으로 선택했다.
문제는 문자열을 계속 반복하기때문에 너무 많은 실행을 해서 시간초과가 난다.
따라서 indexOf를 사용하지않고 문자하나하나를 집어넣을때마다 하는 방식으로 다시 코드를 짰다.

코드(indexOf 사용안함)

import java.util.*;
class Solution {
    public String[] solution(String[] s) {
        String[] answer = new String[s.length];     
        int count =0;
        for(int i=0;i<s.length;i++){
            StringBuilder sb = new StringBuilder();
            StringBuilder num = new StringBuilder();
          
            for(int j=0;j<s[i].length();j++){
                sb.append(s[i].charAt(j));
                if(sb.length()>=3&&sb.charAt(sb.length()-3)=='1'&&sb.charAt(sb.length()-2)=='1'&&sb.charAt(sb.length()-1)=='0'){
                    num.append("110");
                    sb.delete(sb.length()-3,sb.length());
                }
            }
    
            int flag=0;
            if((flag=sb.lastIndexOf("0"))!=-1){
                sb.insert(flag+1,num.toString());
            }else{
                sb.insert(0,num.toString());
            }
            
            answer[count++] =sb.toString();
        }
        
        return answer;
    }
}

의외로 indexOf가 찾았을때 거기서 멈추는것이 아닌 target의 양만큼 계속 돌아간다는것을 알게되었다. 가능하다면 한번의 처리로 해결하는것이 좋은 방식이라는걸 기억하자.