[이코테][Java] 문자열 압축

[문제링크]

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

프로그래머스

---

문제 설명

문자열에서 같은 값이 연속해서 나타는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현한다.

압축하여 표현한 문자열 중 가장 짦은 것의 길이를 구한다.

 

 

 

 

 

문제 풀이

문자를 압축하는 패턴 길이의 범위를 1 ~ (문자열 길이 / 2) 로 해서 각 패턴별로 문자열을 압축하는 방법을 모두 구한다.

그 중에서 문자열의 길이가 가장 짧은 단위를 찾는다.

 

압축 패턴 길이의 범위는 1 ~ (문자열의 길이 / 2)

• 압축 패턴의 길이가 (문자열의 길이)/2를 넘으면 같은 문자열이 반복될 수가 없다.
• ex) 문자열의 길이가 10인 "abcdeabcde"를 길이가 6인 압축 패턴으로 압축해보면, "abcdea", "bcde"로 나누어져 압축할 수 없다.
• substring() 으로 압축 문자열 패턴을 생성한다.

for문을 돌면서 압축 문자열 패턴과 비교

• 같으면 반복횟수(cnt) 증가
• 같지 않으면 {반복횟수 + 압축 문자열 패턴} 추가

 

압축 단위로 나누어 떨어지지 않는 마지막 문자들을 이어 붙인다.

• 문자열이 압축 단위로 나누어 떨어지지 않을 수도 있기 때문에 마지막에 남은 문자를 추가한다.

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

        // 1 ~ s.length()/2 범위로 압축
        for (int i = 1; i <= s.length() / 2; i++) {
            String compressed_str = "";    //i개 단위로 압축한 문자열
            String pre_str = s.substring(0, i); //압축시킬 문자열 패턴
            int cnt = 1;  //문자열의 반복횟수

			//압축 패턴으로 문자열 자르기
            for (int j = i; j <= s.length(); j += i) {
                int end = Math.min(s.length(), j + i);  //끝 인덱스가 문자열 길이보다 넘지 않게 한다.
                String cur_str = s.substring(j, end);

                if (cur_str.equals(pre_str)) {  // 같으면 압축가능: 반복횟수 증가
                    cnt++;
                } else {    //같지 않으면 압축불가능: 문자열에 {반복횟수 + 압축 문자열 패턴} 추가
                    compressed_str += (cnt > 1 ? cnt + pre_str : pre_str);  //cnt=1이면 1은 생략
                    cnt = 1;
                }
                pre_str = cur_str;  //이전 문자열 패턴을 현재 문자열 패턴으로 변경
            }

            compressed_str += pre_str;  //압축 단위 i에 나누어 떨어지지 않은 마지막 문자 붙이기
            answer = Math.min(answer, compressed_str.length());	//
        }
        return answer;
    }
}

 

✔️ 처음에 문제를 풀 때, 압축단위 i에 나누어 떨어지지 않는 문자열의 마지막 부분을 생각하지 못했었다.

---

 

[참고]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈

https://bada744.tistory.com/127