[Programmers] 110 옮기기 (Java)

1.  문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/77886

2.  문제

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

• x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.

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

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

3.  제한사항

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

입출력 예

4.  소스코드

import java.util.*;

class Solution {
    public static String[] solution(String[] s) {
		String[] answer = new String[s.length];
		StringBuilder sb = new StringBuilder();
		for(int index = 0; index < s.length; index++) {
			String str = s[index];
			Stack<Character> stack = new Stack<>();
			int count = 0;
			
			for(int idx = 0; idx < str.length(); idx++) {
				char temp = str.charAt(idx);
				if(stack.size() > 1) {
					char second = stack.pop(), first = stack.pop();
					if(first == '1' && second == '1' && temp == '0') {
						count++;
					} else {
						stack.push(first);
						stack.push(second);
						stack.push(temp);
					}
				} else {
					stack.push(temp);
				}
			}
			
			int idx = stack.size();
			boolean flag = false;
			sb = new StringBuilder();
			
			while(!stack.isEmpty()) {
				if(!flag) {
					if(stack.peek() == '1') idx--;
					else flag = true;
				}
				sb.insert(0, stack.pop());
			}
			if(count > 0) {
				while(count-- > 0) {
					sb.insert(idx, "110");
					idx += 3;
				}
				answer[index] = sb.toString();
			} else {
				answer[index] = s[index];
			}
		}
		return answer;
	}
}