[프로그래머스] Lv2. 문자열 압축

프로그래머스

 

문제 파악

"aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)

 

"abcabcdede"와 같은 문자열은 전혀 압축되지 않음.

문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현

다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법

 

가장 짧은 압축 단위를 찾아 가장 짧은 길이를 찾는 것이 목표!

 

제한 사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

s	result
"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

 

---

접근 방법

문자열 특정 길이만큼 자르고 배열에 저장하는 방식 참고

[Java]특정 길이만큼 문자열 자르기

이 블로그에서 특정 길이만큼 문자열을 자르는 것을 참고하였다.

 

1. 문자열을1,2,3 … 만큼 자르고 개수를 세는 방식으로 진행
2. 처음 1로 잘랐을 때 다음 문자랑 비교를 하고 같으면 카운트 증가, 다르면 초기화
3. 압축된 문자열을 카운트만큼 숫자를 추가하고, 해당 문자를 추가 → 1일 경우에는 추가 안함.
4. 압축을 해서 저장하고 길이 체크해서 누적
5. 다음 문자열 단위로 압축을 진행하고, 가장 작은 길이 반환

---

코드 구현

class Solution {
    public int solution(String s) {
        int minLength = s.length(); 

        for (int i = 1; i <= s.length(); i++) {
            // i단위만큼 분할하여 새로운 배열에 저장
            String[] subStr = s.split("(?<=\\G.{" + i + "})");
            StringBuilder compressed = new StringBuilder(); // 압축결과 저장
            String prev = subStr[0]; // 초기값 (시작 문자)
            int cnt = 1; // 압축된 문자열 수
            
            for (int j = 1; j < subStr.length; j++) {
                if (subStr[j].equals(prev)) {
                    cnt++; // 이전 문자와 같으면 카운트
                } else {
                    if (cnt > 1) compressed.append(cnt); // 1 이상이면 추가
                    compressed.append(prev); // 이전 문자열 압축 

					// 다음 문자로 업데이트 (문자 수도 1로 초기화)
                    prev = subStr[j];
                    cnt = 1;
                }
            }

		// 마지막 문자열 처리
            if (cnt > 1) compressed.append(cnt);
            compressed.append(prev);
            
        // System.out.println(compressed); 
						
		    // 압축된 길이와 기존 최소값 비교
            minLength = Math.min(minLength, compressed.length());
        }

        return minLength;
    }
}