프로그래머스: 110 옮기기 [JAVA]

문제 링크

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

코딩테스트 연습 - 110 옮기기

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 문자열에 대해 부분 문자열 "110"을 제거(스택 방식 적용)하면서 개수 카운트
2. 해당 "110"을 개수만큼 이어붙인 문자열 A 생성
3. 부분 문자열 "110"을 제거한 남은 문자열에 앞의 문자열 A를 넣을 적절한 위치 탐색 후 해당 위치에 삽입

 해결 방법을 찾기가 매우 까다로웠던 문제로, 일종의 법칙을 찾기 위해 매우 엄청난 시간이 필요했다. 결국 제거한 "110" 문자열을 넣어야 하는 위치는 크게 2가지 경우(남은 문자열의 길이가 3 미만인 경우, 3 이상인 경우)이다. 

 우선 남은 문자열의 길이가 3 미만인 경우 만약 남은 문자열이 "1"이거나 "11"이면 "110"을 남은 문자열 앞에 붙여야 한다. 또는 남은 문자열이 "01"이라면 "110"을 남은 문자열의 '0'과 '1' 사이에 넣어야 한다. 그 외에는 단순히 뒤에 붙이면 된다.

 다른 경우인 3 이상인 경우엔 경우가 복잡해지는데, 우선 남은 문자열에서 "111"이 발견된 경우 해당 위치 앞에 "110"을 삽입하면 된다. 그 이에는 남은 문자열의 끝 부분을 살펴봐야 하는데, 만약 끝의 문자열이 "11"인 경우 해당 위치 앞에 "110"을, 아니면 마지막이 "1"인 경우 해당 위치 앞에 "110"을 넣어야 한다.

 앞서 정한 방식을 반복하면 하나의 문자열에 대한 답을 얻을 수 있는데, 자바의 경우 추가적으로 시간 초과를 줄이기 위해 최적화가 필요하다.

 우선 초기 들어온 문자열에서 "110"을 반복적으로 제거하는 경우 우선 while문으로 작성했다가 이를 char 배열에 두고 "110"을 스택처럼 제거하는 방식으로 코드를 작성했다. 

 그 다음 "110"을 반복해 붙이는 과정에서도 최적화가 필요한데, 초기에는 앞선 "110"을 넣는 과정을 while문으로 개수만큼 반복했는데 시간초과를 당했다. 이후 찾아보니 한 번 "110"을 넣은 곳에 어짜피 남은 "110"이 연이어 붙어 들어가기 때문에, 애초에 "110"을 연이어 붙인 긴 문자열을 만든 후 남은 문자열의 적정 위치에 삽입하는 방식으로 코드를 바꿔 작성했다.

 

class Solution {
    public String[] solution(String[] s) {
        String[] answer = new String[s.length];

        for (int i = 0; i < s.length; i++) {//각 문자열들에 대해 변환 적용
            answer[i] = changeString(s[i]);
        }

        return answer;
    }

    String changeString(String string) {
        StringBuilder result = new StringBuilder();//결과용 StringBuilder
        int countOf110 = 0;//문자열 "110" 개수

        if (string.length() <= 3) {//애초에 변환이 필요 없는 길이인 경우
            return string;
        }

//        while (result.indexOf("110") != -1) {//시간 초과된 알고리즘 과정 1
//            ++countOf110;
//            result.delete(result.indexOf("110"), result.indexOf("110") + 3);
//        }

        char[] remove110 = new char[string.length()];//문자열을 순차대로 담을 char 배열
        remove110[0] = string.charAt(0);
        remove110[1] = string.charAt(1);
        
        int remove110Pos;
        remove110Pos = 1;

        for (int i = 2; i < string.length(); i++) {//스택 방식과 같은 제거 알고리즘
            if (string.charAt(i) == '0') {
                if (remove110Pos >= 1 && remove110[remove110Pos] == '1' && remove110[remove110Pos - 1] == '1') {
                    ++countOf110;
                    remove110Pos -= 2;
                    continue;
                }
            }
            remove110[++remove110Pos] = string.charAt(i);
        }

        for (int i = 0; i <= remove110Pos; i++) {//남은 문자열 생성
            result.append(remove110[i]);
        }

//        while (countOf110 != 0) { //시간 초과된 알고리즘 3과정
//            if (result.toString().length() < 3) {
//                if (result.toString().equals("1") || result.toString().equals("11")) {
//                    result.insert(0, "110");
//                } else if (result.toString().equals("01")) {
//                    result.insert(1, "110");
//                } else {
//                    result.append("110");
//                }
//            } else {
//                int pos = result.indexOf("111");
//
//                if (pos != -1) {
//                    result.insert(pos, "110");
//                } else if (result.substring(result.length() - 2).equals("11")) {
//                    result.insert(result.length() - 2, "110");
//                } else if (result.substring(result.length() - 1).equals("1")) {
//                    result.insert(result.length() - 1, "110");
//                } else {
//                    result.append("110");
//                }
//            }
//            --countOf110;
//        }

        StringBuilder string110 = new StringBuilder();

        for (int i = 0; i < countOf110; i++) {//문자열 110을 미리 연이어 붙여 놓음
            string110.append("110");
        }

        if (result.toString().length() < 3) {//남은 문자열의 길이가 3미만
            if (result.toString().equals("1") || result.toString().equals("11")) {
                result.insert(0, string110);
            } else if (result.toString().equals("01")) {
                result.insert(1, string110);
            } else {
                result.append(string110);
            }
        } else {//남은 문자열의 길이가 3이상
            int pos = result.indexOf("111");

            if (pos != -1) {
                result.insert(pos, string110);
            } else if (result.substring(result.length() - 2).equals("11")) {
                result.insert(result.length() - 2, string110);
            } else if (result.substring(result.length() - 1).equals("1")) {
                result.insert(result.length() - 1, string110);
            } else {
                result.append(string110);
            }
        }

        return result.toString();
    }
}

결과