문제링크

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

구현방법

문자열의 길이는 최대 1000이기 때문에 이중 for문을 돌려도 되겠다고 생각했고, 압축문자는 최대 절반까지만 체크하면되겠다고 생각했습니다. 절반인 이유는 절반을 넘어갈 경우 압축이 되지않기 때문에 선택했습니다.

boolean을 통해서 마지막 꼬리 부분이 현재 압축할 문자의 개수보다 작은 경우 잘리는 것을 방지

만약 잘리기 전까지 같은 문자열이 반복되다가 짤릴 경우도 체크

뒷 부분이 잘리지 않고 끝나는 경우

1. 반복되다가 끝나는 경우 -> 마지막에 cnt가 1보다 큰경우 cnt + str을 통해서 붙여준다.
2. cnt가 1이하인경우 -> 반복이 되지않았기 때문에 마지막 부분을 붙여준다.

안쪽 for문이 다돌고 만들어진 문자열의 길이와 이전까지 했던 길이와 길이 체크를 해서 작은 길이로 바꿔준다.

다시 코테를 준비하다보니 구현을하는데 꽤 오랜시간이 걸렸습니다. 좀더 많이 풀어보면서 다시 감각을 찾아야겠습니다.

구현알고리즘

구현

CODE

/**
 * 문자열 압축
 * 구현 문제
 * 최대 길이가 1000이기 때문에 2중 for문을 돌려도 시간초과가 발생하지않는다.
 * 압축 문자열은 절반까지 확인 -> 어쩌피 절반을 넘어가면 압축이 되지않음.
 */
class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        if (s.length() == 1)
            return 1;

        //절반까지만 체크
        for (int idx = 1; idx <= s.length() / 2; idx++) {
            String str = s.substring(0, idx);
            int cnt = 0;
            int part = 0;
            boolean flag = true;
            String newOne = "";
            for (; part < s.length(); part += idx) {
                String part_st = "";
                //길이 범위안쪽일경우
                if (part + idx <= s.length()) {
                    part_st = s.substring(part, part + idx);
                } else {
                    flag = false;
                    break;
                }
                if (str.equals(part_st)) {
                    cnt += 1;
                } else {
                    if (cnt <= 1) {
                        newOne += str;
                    } else {
                        newOne += cnt + str;
                    }
                    str = part_st;
                    cnt = 1;
                }
            }
            if (!flag && cnt > 1) {
                newOne = newOne + cnt + str + s.substring(part);
            } else if (!flag) {
                newOne = newOne + str + s.substring(part);
            }


            if (flag && cnt > 1) {
                newOne += cnt + str;
            }
            if (flag && cnt <= 1) {
                newOne += str;
            }
            answer = Math.min(answer, newOne.length());

        }

        return answer;
    }
}