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

[문제]

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

코딩테스트 연습 - 문자열 압축

---

[문제 풀이]

문자열을 압축해서 가장 문자열의 길이가 작은 것을 return 하도록 문제를 풀어야합니다.

s의 길이는 1이상 1,000 이하이고 가장 길이가 작은 것을 구하므로 문자열의 압축방식을 1부터 진행하여 결과값을 비교하면 됩니다. 여기서 문자열을 압축할때 전체 문자열의 반이상이 넘어가면 압축을 하지 못하므로 문자열의 반까지만 압축을 진행하면 됩니다. 압축할 문자열을 선정하고 압축이 되는 문자가 있는지 계속 확인하면서 문자열의 길이만 계산을 하면 됩니다.

 

 

 

• 압축하는 방법 1부터 ~ 문자열 길이의 반까지
• 현재 문자를 가르치는 위치변수 pos를 만듭니다.
• 현재위치부터 압축하려는 문자의 개수 까지 압축되는 문자열을 만듭니다.
• 압축되는 문자열이 있는지 계속 확인 해줍니다.
• 압축된 문자가 있으면 길이를 조정합니다.
• 압축된 문자열의 길이와 입력받은 문자열의 길이를 비교해 작은값을 가집니다.
• 작은값을 출력합니다.

 

 

---

[소스 코드]

 

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

        //압축하는 방법 1부터 ~ 반까지  i = 압축할 수
        for (int i = 1; i <= n / 2; i++) {
            int pos = 0; //가르키는 위치
            int len = n;

            while (pos + i <= s.length()) {
                String temp = s.substring(pos, pos + i);
                pos += i;

                int cnt =0; //압축되는 문자의 수

                //압축되는 문자가 있는지 확인
                while (pos + i <= s.length()) {
                    if (temp.equals(s.substring(pos, pos + i))) {
                        cnt++; //압축됨
                        pos += i;
                    }else{
                        break;
                    }
                }

                //압축된 문자가 있어야 길이를 조정한다.
                if (cnt > 0) {
                    len -= i * cnt; //압축한 길이 * 압축된 수

                    //aaaaa = 5a // aaaaaaaaaa = 10a 글자가 10, 100, 1000 단위일때마다 늠!
                    if (cnt < 9) {
                        len += 1;
                    } else if (cnt < 99) {
                        len += 2;
                    } else if (cnt < 999) {
                        len += 3;
                    } else{
                        len += 4;
                    }

                }
            }
            if (len < answer) {
                answer = len;
            }
        }

        return answer;
    }
}