Programmers - 110옮기기 with JAVA

 

 

 

 

문제

1과 0으로 이루어진 문자열에서 "110"들을 찾고 나머지 수와 "110"들을 합쳐 가장 작은 수를 만들어라

 

 

 

로직

1. 모든 "110"을 찾는다.

-> 이 때, Stack을 이용해 한번의 반복에 모든 "110" 을 찾아야 시간복잡도가 충족된다.

2. 뒤에서 부터 가장 가까운 0을 찾고 모든 "110"을 해당 0 뒤에 붙여주어 가장 작은 숫자를 만든다.

-> 항상, 0이 앞에 있을 수록 작기 때문이다.

 

 

 

 

 

 

코드

import java.util.*;
class Solution {
    public List<String> solution(String[] s) {
        List<String> answer = new ArrayList<>();
        for(String now : s){
            if(now.length() <= 3){
                answer.add(now);
                continue;
            }
            String new_now = find(now);
            int count = (now.length()-new_now.length())/3;
            now = new_now;
            int index = -1;
            for(int i=now.length()-1; i>=0; i--){
                if(now.charAt(i) == '0'){
                    index = i;
                    break;
                }
            }
            StringBuilder sb = new StringBuilder();
            if(index == -1){
                for(int i=0; i<count; i++){
                    sb.append("110");
                }
                sb.append(now);
                answer.add(sb.toString());
            }
            else{
                sb.append(now.substring(0, index+1));
                for(int i=0; i<count; i++){
                    sb.append("110");
                }
                sb.append(now.substring(index+1, now.length()));
                answer.add(sb.toString());
            }
        }
        return answer;
    }
    public static String find(String now){
        StringBuilder sb = new StringBuilder();
        List<Character> check = new ArrayList<>();
        for(char c : now.toCharArray()){
            check.add(c);
            if(check.size() < 3){
                continue;
            }
            while(true){
                int len = check.size();
                if(len-3 < 0){
                    break;
                }
                if(check.get(len-1) == '0' && check.get(len-2) == '1' 
                   && check.get(len-3) == '1'){
                    for(int i=0; i<3; i++){
                        check.remove(check.size()-1);
                    }
                }
                else{
                    break;
                }
            }
        }
        for(char c : check){
            sb.append(c);
        }
        return sb.toString();
    }
}