[lv3] 110 옮기기

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

 

 

1. 모든 "110" 제거

주어진 문자열에서 "110"을 모두 추출한다.

 

111100 과 같이 하나의 "110"을 추출했을 때 나머지가 다시 "110"을 이룰 수 있으므로,

StringBuilder을 Stack처럼 활용한다.

(괄호 유효성 검사 문제로 빗대면, "11"을 "{"로, 0을 "}"로 놓는다.)

 

2. 사전 순으로 앞서게 배치?

경우의 수를 생각해보면, "110"은 "111"인 부분을 replace할 때만 사전 순으로 앞선다.

000 ~ 101인 부분을 대체한다면 사전 순을 늦추기만 한다.

 

3. 반례

2번 논리로만 접근하면 반례가 있다.

입력 : 111000

오답 : 110100

정답 : 100110

 

4. 해결 방법

모든 "110"을 제거한 문자열에서 "0"이 마지막으로 등장한 부분을 찾는다.

"0"이 없다면, 숫자가 더 이상 없거나 "1"만 남은 경우이므로, 맨 앞에 "110"들을 배치시킨다.

"0"이 있다면,  "0"이 마지막으로 등장한 부분 뒤에 "110"들을 배치시킨다.

 

class Solution {
    public String[] solution(String[] s) {

        int idx = 0;
        String[] answer = new String[s.length];

        for(String ns : s) {
            int NS = ns.length();

            StringBuilder sub = new StringBuilder();
            StringBuilder del = new StringBuilder();

            for(int i=0; i<NS; i++) {

                int SB = sub.length();
                if(SB > 1 && ns.charAt(i) == '0' &&
                        sub.charAt(SB - 1) == '1' && sub.charAt(SB - 2) == '1') {

                    del.append("110");
                    sub.delete(SB-2, SB);
                }
                else sub.append(ns.charAt(i));
            }

            int last = sub.lastIndexOf("0");

            answer[idx++] = last == -1 ? del.toString() + sub.toString() :
                    sub.substring(0, last+1) + del.toString() + sub.substring(last+1);
        }

        return answer;
    }
}