[프로그래머스] 110 옮기기 (JAVA)

문제 설명

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

Code

1트

import java.util.*;
class Solution {
    public String[] solution(String[] s) {
        String[] ret = new String[s.length];
        for(int i=0 ; i<s.length ; i++) {
        	ret[i] = helper(s[i]);
        }
        return ret;
    }
    public static String helper(String s) {
		StringBuilder sb = new StringBuilder();
		StringBuilder plus = new StringBuilder();
		Stack<Character> stack = new Stack<>();
		int cnt1=0;
		for(int i=0 ; i<s.length() ; i++) {
			char c = s.charAt(i);
			if(c=='1') {
				cnt1++;
				stack.push(c);
			} else {
				if(cnt1>=2) {
					plus.append("110");
					cnt1-=2;
					stack.pop();
					stack.pop();
				} else {
					cnt1=0;
					stack.push(c);
				}
			}
		}
		
		if(plus.length()==0) return s;
		if(stack.size()==0) return plus.toString();
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		sb.reverse();
		
		return getString(sb, plus);
	}
    
    public static String getString(StringBuilder sb, StringBuilder plus) {
		if(sb.indexOf("0")==-1) {
			sb.insert(0, plus);
		} else {
			sb.insert(sb.lastIndexOf("0")+1, plus);
		}
		return sb.toString();
	}
    
}

: Stack을 사용해서 string을 만들었고, POP하여 reverse한다는 추가 작업이 필요하다.
테스트 1 〉 통과 (129.95ms, 128MB)
테스트 2 〉 통과 (120.31ms, 106MB)
테스트 3 〉 통과 (119.47ms, 104MB)
테스트 4 〉 통과 (149.22ms, 118MB)
테스트 5 〉 통과 (118.96ms, 121MB)
테스트 6 〉 통과 (90.09ms, 116MB)
테스트 7 〉 통과 (87.14ms, 104MB)
테스트 8 〉 통과 (86.15ms, 98.6MB)
테스트 9 〉 통과 (110.21ms, 148MB)
테스트 10 〉 통과 (136.64ms, 155MB)
테스트 11 〉 통과 (107.42ms, 173MB)
테스트 12 〉 통과 (136.67ms, 145MB)
테스트 13 〉 통과 (118.71ms, 154MB)
테스트 14 〉 통과 (141.94ms, 166MB)
테스트 15 〉 통과 (105.40ms, 149MB)
테스트 16 〉 통과 (170.53ms, 151MB)
테스트 17 〉 통과 (122.65ms, 161MB)
테스트 18 〉 통과 (63.51ms, 102MB)
테스트 19 〉 통과 (54.83ms, 115MB)
테스트 20 〉 통과 (53.86ms, 105MB)
테스트 21 〉 통과 (66.22ms, 116MB)

2트

class Solution {
    public String[] solution(String[] s) {
        String[] ret = new String[s.length];
        for(int i=0 ; i<s.length ; i++) {
        	ret[i] = helper(s[i]);
        }
        return ret;
    }
    public String helper(String s) {
		StringBuilder sb = new StringBuilder();
		StringBuilder plus = new StringBuilder();
		
		for(int i=0 ; i<s.length() ; i++) {
			char c = s.charAt(i);
			sb.append(c);
			if(sb.length()>=3 && sb.charAt(sb.length()-3)=='1' && sb.charAt(sb.length()-2)=='1'  && sb.charAt(sb.length()-1)=='0') {
				plus.append("110");
				sb.delete(sb.length()-3, sb.length());
			}
		}
		if(plus.length()>0) {
			if(sb.indexOf("0")==-1) {
				sb.insert(0,plus);
			} else {
				sb.insert(sb.lastIndexOf("0")+1,plus);
			}
		}
		return sb.toString();
	}
}

: StringBuilder 로만 그냥 사용함.
테스트 1 〉 통과 (60.64ms, 121MB)
테스트 2 〉 통과 (57.48ms, 110MB)
테스트 3 〉 통과 (42.77ms, 105MB)
테스트 4 〉 통과 (57.16ms, 104MB)
테스트 5 〉 통과 (79.94ms, 110MB)
테스트 6 〉 통과 (77.29ms, 91.3MB)
테스트 7 〉 통과 (51.20ms, 106MB)
테스트 8 〉 통과 (52.19ms, 104MB)
테스트 9 〉 통과 (53.97ms, 146MB)
테스트 10 〉 통과 (59.81ms, 141MB)
테스트 11 〉 통과 (65.07ms, 137MB)
테스트 12 〉 통과 (71.12ms, 148MB)
테스트 13 〉 통과 (68.25ms, 144MB)
테스트 14 〉 통과 (94.37ms, 144MB)
테스트 15 〉 통과 (96.00ms, 146MB)
테스트 16 〉 통과 (73.09ms, 135MB)
테스트 17 〉 통과 (69.47ms, 137MB)
테스트 18 〉 통과 (68.56ms, 98.4MB)
테스트 19 〉 통과 (77.04ms, 103MB)
테스트 20 〉 통과 (64.67ms, 98.7MB)
테스트 21 〉 통과 (70.17ms, 96.1MB)