🔗 링크

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

👾 문제

압축할 문자열 s가 매개변수로 주어질 때,

1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 구해야한다.

👀 예제로 문제 파악하기

입력 : s aabbaccc

1개 단위로 자를 때 : 2a2ba3c

2개 단위로 자를 때 : aabbaccc

3개 단위로 자를 때 : aabbaccc

4개 단위로 자를 때 : aabbaccc

따라서 가장 작은 길이는 7(2a2ba3c)이다.

---

입력 : s ababcdcdababcdcd

1개 단위로 자를 때 : ababcdcdababcdcd

2개 단위로 자를 때 : 2ab2cd2ab2cd

3~7개 단위로 자를 때 : ababcdcdababcdcd

8개 단위로 자를 때 : 2ababcdcd

따라서 가장 작은 길이는 9(2ababcdcd)이다.

😮 알고리즘 풀이 순서

푼 방법은 i개의 갯수만큼 문자열을 잘라 현재 문자열과 전 문자열을 비교하여 압축을 하는 방법이다.

1. for문을 s의 길이 / 2만큼 돌린다. (변수 이름 : i)
   • i는 몇 글자씩 자를지를 결정한다.
   • 길이 / 2를 넘으면 압축이 불가능하기 때문에 조건식을 저렇게 두었다.
   • compression를 호출한다.
2. compression
   • 압축되었는지 여부를 확인할 count 변수를 1로 초기화한다.
   • s.length() + i만큼 for문을 돌리고, 증감식은 j += i로 설정한다. (변수 이름 : j)
     • 전 문자열과 비교할 현재 문자열을 구한다.
       • 현재 문자열이 없으면 (전 문자열이 마지막 문자열이면) 빈 문자열
       • 현재 문자열이 마지막 문자열이면 j부터 끝까지
       • 그외는 j + i
     • j가 0이 아니면 (현재 문자열이 맨 처음이면 비교를 하지 않는다.)
       • 전 문자열과 현재 문자열을 비교해서 같으면
         • count++
       • 전 문자열과 현재 문자열이 다르고 count가 2회 이상이면 (압축 가능 상태)
         • 전체 압축 문자열 += count + 전 문자열
       • 그렇지 않으면
         • 전체 압축 문자열 += 전 문자열
     • 현재 문자열을 전 문자열로 바꿔준다.
     • 반복이 모두 끝나면 전체 압축 문자열을 리턴한다.
3. compression 결과 값의 길이와 min의 길이를 비교해서 더 작은 것을 min에 대입한다.

👨‍💻 코드

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

      for (int i = 1; i <= s.length() / 2; i++) {
        int compLeng = compression(s, i).length();
        min = Math.min(min, compLeng);
      }

      return min;
    }

    /**
     * 문자열 압축
     *
     * @param str 입력받은 문자열
     * @param i i값
     * @return 압축된 문자열
     */
    private String compression(String str, int i) {

      int count = 1;
      String compression = "";
      String pattern = "";

      for (int j = 0; j <= str.length() + i; j += i) {

        String nowStr;

        // 전 문자열과 비교할 현재 문자열
        if (j >= str.length()) { // 현재 문자열이 없을 때
          nowStr = "";
        } else if (str.length() < j + i) { // 마지막 현재 문자열일 때
          nowStr = str.substring(j);
        } else {
          nowStr = str.substring(j, j + i); // 그 외
        }

        // 1. 전 문자열이랑 똑같은지 비교한다. (맨 처음이면 비교 X)
        if (j != 0) {
          if (nowStr.equals(pattern)) { // 똑같으면
            count++;
          } else if (count >= 2) { // 다르고 count가 2회 이상이면 압축 가능
            compression += count + pattern;
            count = 1;
          } else { // 압축 불가능하면 그냥 그대로 문자열 이어붙이기
            compression += pattern;
          }
        }
        // 2. i 길이만큼 문자열을 자른다.
        pattern = nowStr;
      }

      return compression;
    }

    @Test
    public void 정답() {
      Assert.assertEquals(7, solution("aabbaccc"));
      Assert.assertEquals(9, solution("ababcdcdababcdcd"));
      Assert.assertEquals(8, solution("abcabcdede"));
      Assert.assertEquals(14, solution("abcabcabcabcdededededede"));
      Assert.assertEquals(17, solution("xababcdcdababcdcd"));
    }
}