[프로그래머스]#77886 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

입출력

s	result
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

입출력 예

• 다음 그림은 "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;
    }
}