[알고리즘] 프로그래머스 문자열 압축 -2020 KAKAO BLIND RECRUITMENT-

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

프로그래머스

 

 

프로그래머스 프로그래머스 문자열 압축 -2020 KAKAO BLIND RECRUITMENT- 를 풀어봤습니다.

처음 생각난게 split 특성으로 푸는거여서 그대로 풀었습니다. 중간에 다른 쉬운방법도 생각났는데 외골수 성향이 있어서 더럽게 풀어도 이대로 풀어버렸네요.. ㅠ  너무 더럽게 풀었다는...

늦었으니 내일 생각나면 다른 방법으로 풀어볼까 합니다.

 

자바 문자열 split의 다음과 같은 특성을 이용했습니다.

예시) "aabbaccc"

"a" 로 split 할 경우 String[] 으로 {"", "", bb, "", ccc}

이런식으로 됩니다. 그래서 빈문자열("") 의 연속된 개수로 a가 2개 연속왔구나를 알 수 있습니다.

 

예시2) "aaaa"

"a" 로 split 할 경우 String[] 은 {""} 가 아니라 empty 상태 {} 가 됩니다. (기준인 a 이외의 문자가 없는 경우) 

이것으로 a밖에 없다는 것을 알 수 있습니다.

 

나머지 설명은 주석에 작성해놨습니다. 

class Solution {

    public int solution(String s) {
        int answer = 1000; // 최대치로 초기화
        int index = 0; // 문자열의 인덱스(포인터) 역할
        String result = "";

        //문자열 1의 길이인 경우 (한가지 케이스 예외처리)
        if (s.length() == 1) {
            return 1;
        }

        // 한개부터 최대 나눌 수 있는 개수(s.lengt/2) 만큼 반복
        for (int i = 1; i <= (s.length() / 2); i++) {
            index = 0;
            result = "";
            while (true) {
                String standard = ""; // 자르는 기준 문자열
                if (index + i > s.length()) { //index가 최대길이 오버한 경우 최대길이로 조정
                    standard = s.substring(index);
                } else {
                    standard = s.substring(index, index + i);
                }
                String remainStr = s.substring(index); // 압축 안된 문자열
                String[] splitArr = remainStr.split(standard); // 압축 안된 문자열을 기준 문자열로 split
                int compressCount = 0; // 압축 카운트
                while (true) {
                    if (splitArr.length == 0) { // standard 로 끝문자열까지 압축 할 수 있는 경우, 즉 마지막까지 standard 로 압축가능
                        compressCount = remainStr.length() / standard.length(); //
                        break;
                    }
                    if (splitArr[compressCount].equals("")) { // standard 로 압축가능한 개수 +1
                        compressCount++;
                    } else { // standard 로 압축 불가
                        break;
                    }
                }
                index += standard.length() * compressCount; // 다음 불러올 문자열 index 증가
                if (compressCount == 1) { // 압축 하나인 경우
                    result += standard;
                } else { // 두개 이상인 경우 앞에 압축개수 붙여줌
                    result += "" + compressCount + standard;
                }
                if (index >= s.length()) { // 문자열 끝까지 압축실행 했을 경우
                    if (answer >= result.length()) { // 지금까지 최솟값 보다 이번 압축결과가 더 작으면 교체
                        answer = result.length();
                    }
                    break;
                }
            }
        }
        return answer;
    }
}

 

 

좀 더럽게 푼거같네요. 허허 .. 다른 풀이도 해볼까 합니다.

프로그래머스 다른사람풀이를 살짝봤는데 코드가 다들 긴 거 같긴 합니다

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다!!