프로그래머스 3단계 : 110 옮기기 (Java 자바)

 

프로그래머스

 

문제 설명

 

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

 

입출력 예

 

 

 

 

풀이

 

class Solution {
    public String[] solution(String[] s) {
        String[] ret = new String[s.length]; // 결과를 저장할 배열
        for (int i = 0; i < s.length; i++) {
            ret[i] = helper(s[i]); // 각 문자열을 변형하여 결과 배열에 저장
        }
        return ret; // 결과 배열 반환
    }

    public String helper(String s) {
        StringBuilder sb = new StringBuilder(); // 변형된 문자열을 저장할 StringBuilder
        StringBuilder plus = new StringBuilder(); // "110"을 뽑아서 삽입할 StringBuilder

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            sb.append(c); // 현재 문자를 변형된 문자열에 추가

            // "110" 패턴이 발견되면 plus StringBuilder에 추가하고 변형된 문자열에서 제거
            if (sb.length() >= 3 && sb.charAt(sb.length() - 3) == '1' && sb.charAt(sb.length() - 2) == '1' && sb.charAt(sb.length() - 1) == '0') {
                plus.append("110");
                sb.delete(sb.length() - 3, sb.length());
            }
        }

        // plus에 "110"이 있을 경우, 변형된 문자열에 추가
        if (plus.length() > 0) {
            if (sb.indexOf("0") == -1) {
                sb.insert(0, plus); // 문자열에 "0"이 없으면 plus를 맨 앞에 추가
            } else {
                sb.insert(sb.lastIndexOf("0") + 1, plus); // "0"이 있는 위치 뒤에 plus를 추가
            }
        }

        return sb.toString(); // 변형된 문자열 반환
    }
}