[ 프로그래머스 / Programmers Level 3 ] 110 옮기기 ( 자바 / JAVA )

https://programmers.co.kr/learn/courses/30/lessons/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

예제 입출력

---

입출력 예 #1

• 다음 그림은 "1110"을 "1101"로 만드는 과정을 나타낸 것입니다.

• "1101"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "1101"을 담아야 합니다.
• 다음 그림은 "100111100"을 "100110110"으로 만드는 과정을 나타낸 것입니다.

• "100110110"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "100110110"을 담아야 합니다.
• 그림에 나온 방식 말고도 다른 방법으로 "100110110"을 만들 수 있습니다.
• 다음 그림은 "0111111010"을 "0110110111"로 만드는 과정을 나타낸 것입니다.

• "0110110111"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "0110110111"을 담아야 합니다.
• 그림에 나온 방식 말고도 다른 방법으로 "0110110111"을 만들 수 있습니다.

풀이

---

stack에 110을 제외하고 PUSH 

stack 내의 문자들을 Stringbuilder에 저장하면서 가장 마지막 0의 위치 찾기 ‼️

원래 문자에 110 이 존재하지 않았었다면, 원본 그대로 저장

존재했다면, 마지막 0 뒤에 '110'을 찾은 갯수 만큼 추가

코드

---

import java.util.Stack;

public class PR_110옮기기 {
    public static 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() > 1){
                    char y = stack.pop();
                    char x = stack.pop();

                    if(x == '1' && y == '1' && z == '0')
                        cnt++;
                    else{
                        stack.push(x);
                        stack.push(y);
                        stack.push(z);
                    }
                }
                else
                    stack.push(z);
            }

            int idx = stack.size();
            boolean flag = false;
            sb = new StringBuilder();

            // 0의 마지막 위치 찾기 
            while(!stack.isEmpty()){
                if(!flag){
                    if(stack.peek() == '1') 
                        idx--;
                    else
                        flag = true;
                }
                sb.insert(0, stack.pop());
            }

            if(cnt > 0){
                while(cnt-- > 0){
                    sb.insert(idx, "110");
                    idx += 3;
                }
                answer[i] = sb.toString();
            }
            else
                // 110 이 없다는 의미이므로 그대로 
                answer[i] = s[i];
        }

        return answer;
    }

    public static void main(String[] args) {
        String[] s = {"100111100"};

        String[] answer = solution(s);
    }
}