[프로그래머스] 77886 - 110 옮기기 (Java)

문제 파악

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

프로그래머스

풀이

크게 두 가지 구현이 필요하다

1. 주어진 문자열에서 110을 모두 제거
2. 규칙에 따라 110들을 사전순으로 이른 위치에 삽입

1. 주어진 문자열에서 110을 모두 제거

StringBuffer를 활용하여 주어진 문자열을 순환하며 가장 끝자리가 110이라면 삭제하고,
그렇지 않으면 계속 버퍼에 쌓아주자

2. 규칙에 따라 110들을 사전순으로 이른 위치에 삽입

규칙을 찾기 위해 세 자리까지만 나열해 보도록 하자..

한 자리 수	두 자리 수	세 자리 수
0 ➡️ 0[110] 1 ➡️ [110]1	00 ➡️ 00[110] 10 ➡️ 10[110] 01 ➡️ 0[110]1 11 ➡️ [110]11	000 ➡️ 000[110] 100 ➡️ 100[110] 010 ➡️ 010[110] 001 ➡️ 00[110]1 101 ➡️ 10[110]1 011 ➡️ 0[110]11 111 ➡️ [110]111 110 ➡️ 110[110] 이미 모두 제거된 상태

위 규칙을 살펴보면 다음 규칙을 확인할 수 있다.

• 가장 마지막 0의 오른쪽에 110을 삽입
• 남은 문자열에 0이 없다면 가장 앞에 삽입

이 두 과정을 구현하면 아래와 같다.

코드

public class Main {
    public String[] solution(String[] s) {
        String[] answer = new String[s.length];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = replacedResult(s[i]);
        }
        return answer;
    }

    private String replacedResult(String s) {
        String bf = s;
        s = remove110(s);
        String com = "110".repeat((bf.length() - s.length()) / 3);
        if (s.length() == 0) {
            return com;
        }
        int fZero = s.lastIndexOf("0");
        int insertPos = fZero == -1 ? 0 : fZero + 1;
        return s.substring(0, insertPos) + com + s.substring(insertPos);
    }

    public static String remove110(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (sb.length() >= 3 &&
                    sb.charAt(sb.length() - 3) == '1' &&
                    sb.charAt(sb.length() - 2) == '1' &&
                    sb.charAt(sb.length() - 1) == '0') {
                sb.delete(sb.length() - 3, sb.length());
            }
        }
        return sb.toString();
    }
}