문자열 압축

Posted on Edited on In , ,

문제정의

문자열을 일정 단위로 끊어서 압축하려고 한다(ex. abab -> 2ab). 몇 개 단위로 끊어서 압축이 가장 많이 된 문자열의 길이를 계산하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class StringCompress {

    //프로그래머스 문제풀이 level2 문자열 압축

    public static void main(String[] args)
    {
        String s = "aabbcc";
        StringBuffer buff = new StringBuffer();
        int answer = 2000;
        int cnt = 1;
        if(s.length() == 1)
            answer = 1;
        for(int cut = 1; cut <= s.length()/2; cut++)
        {
            String key = s.substring(0, cut);
            buff.delete(0, buff.length());
            cnt = 1;
            for(int i = cut; i < s.length(); i += cut)
            {
                if(i + cut > s.length())
                {
                    if(cnt > 1)
                        buff.append(cnt);
                    buff.append(key);
                    buff.append(s.substring(i, s.length()));
                    break;
                }

                else if(key.equals(s.substring(i, i+cut)))
                {
                    cnt++;
                    if(i == s.length()-1 || i+cut == s.length())
                    {
                        buff.append(String.valueOf(cnt));
                        buff.append(key);
                    }
                }

                else
                {
                    if(cnt > 1)
                        buff.append(String.valueOf(cnt));
                    buff.append(key);
                    if(i + cut >= s.length())
                    {
                        buff.append(s.substring(i, s.length()));
                        break;
                    }
                    key = s.substring(i, i+cut);
                    cnt = 1;
                }
            }
            String str = buff.toString();
            answer = Math.min(answer, str.length());
        }
        System.out.println(answer);
    }
    
}
필자는 이 코드가 굉장히 마음에 안드는데 일단 많이 조잡하다. 핵심 아이디어는 간단하다. 앞에서부터 문자열을 끊어서 key으로 만든 뒤, 압축이 가능하다면 cnt를 계산하여, 넣어주고 아니면 문자열 그대로를 넣어준다. 만약 문자열이 남아버리면 한꺼번에 넣어준다. 필자는 세부적인 구현에서 if문을 덕지덕지 붙여서 통과했다. 질문하기에서 봤던 테스트 케이스를 참고해서 통과했으니, 세부적인 구현 능력을 좀 더 길러야겠다.

시간복잡도는 문자열의 길이를 n이라 할 때, 최대 \(n^2/2\) 만큼 반복하므로 \(O(n^2)\)이다.

테스트