[level2] 프로그래머스 - 문자열 압축(JAVA)

잘 풀리지 않아서
유튜브 해설 강의를 조금 참고해서
다시 풀어보았습니다.
https://youtu.be/HFnyxCQe_2g

 

 

- 1부터 len(문자열 길이 / 2)만큼의 길이로 잘라서 압축해 본다.

 

 

- index값을 여러개를 사용하다보니 헷갈렸는데,
   유튜브를 보니 그냥 i라는 변수를 for 밖으로 빼내서 모든 for문에 대해 사용하는 것이 안 헷갈리고 편하다.

 

- str =  i부터 i + size까지 문자열을 자른다.   => 나와 같은게 있는지 비교할 기준이 될 문자열

- new_str = size만큼 뒤로 가서 그 다음 문자열을 또 size만큼 자른다.

만약 str과 new_str이 같다면,
- i를 또 size만큼 뒤로 이동 시킨다.
- 같은 문자열이 나온 횟수를 저장하는 cnt를 증가시킨다.
- 문자열을 size크기만큼 또 자르고, 비교하는 과정(for문)을 계속 반복한다.

만약 str과 new_str이 다르다면,
- 다시 기준이 되는 문자열(str)을 현재 위치(i)부터 자른 것으로 바꿔준 뒤, 비교해야 하므로 break시켜준다.

 

 

- cnt가 0보다 크다면, 자기 자신과 같은 문자열이 있다는 것!!

- cnt + 1한 값을 문자열로 바꾸어주고 이것의 길이를 구한다.

여기서 주의할 점!!!!
aa => 2a이다. 

즉, 자신의 개수도 cnt에 포함이 되어야 한다.

이것을 간과하면, 10이어야 할 것이 9가 되어 문자열 길이가 달라지게 된다.

 

 

- sum은 현재, 문자열 s의 길이 이므로 

압축해서 사라진 문자의 길이를 빼주고
= cnt * size = 기준과 같은 문자열의 수 * 문자열의 길이
     ex) aaa 가 3a가 될때, a가 2개 사라진다.

위에서 구한 s_cnt의 길이을 더해준다.
     ex) aaa 가 3a가 될때, (cnt+1)의 값이 앞에 붙는다.

 

 

- 하지만 len이 1인 경우, 애초에 자르지 못해 for문을 돌지 않는다.
   따라서 for문 전에 len가 1이면 그냥 return 1(원래의 문자열 길이)를 리턴하도록 해주어야 한다.

 

 

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

        int len = s.length();

        if (len == 1) return 1;

        for (int size = 1; size <= len / 2; size++) {
            int i = 0; // index 번호
            int sum = len;

            for (; i + size <= len;) {
                String str = s.substring(i, i + size);
                i += size;

                int cnt = 0;
                for (; i + size <= len;) {
                    String new_str = s.substring(i, i + size);
                    if (str.equals(new_str)) {
                        cnt++;
                        i += size;
                    } else
                        break;
                }

                String s_cnt = (cnt + 1) + "";  // 개수는 자기자신 포함
                if (cnt > 0)
                    sum = sum - cnt * size + s_cnt.length();
            }
            answer = Math.min(answer, sum);
        }

        return answer;
    }
}