문제

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

코드

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
public int solution(String s) {
    int stringLength = s.length();

    StringBuilder result = new StringBuilder();
    String origin = new String();
    char[] tochar = s.toCharArray();
    int min = Integer.MAX_VALUE;

    for (int i = 1; i <= stringLength / 2; i++) {
        int compression = 1;
        result.setLength(0);
        origin = new String(tochar, 0, i);

        String nextWord = new String();
        for (int j = i; j < stringLength; j+=i) {
            if (j + i > stringLength) {
                nextWord = s.substring(j, stringLength);
            } else {
                nextWord = new String(tochar, j , i);
            }

            if (origin.equals(nextWord)) {
                ++compression;
            } else {
                if (compression != 1) {
                    result.append(compression);
                }

                result.append(origin);

                origin = nextWord.toString();
                compression = 1;
            }
        }

        if (compression != 1) {
            result.append(compression);
        }

        result.append(origin);

        if (min > result.length()) {
            min = result.length();
        }
    }

    int answer = min > stringLength ? stringLength : min;
    return answer;

흐름

  1. 문자열을 반으로 나눠서 2개로 나눈 것 보다 짧을 수 없으므로 문자열 길이 / 2 한 값 만큼 반복

  2. 비교 할 문자열을 구함(origin)

    • 처음엔 1개 짜리 이후엔 2개, 3개, … 증가 할 수 있도록 i를 증가 시키면서 i 번째 까지 자름

  3. i 번째 문자 이후로 비교 할 문자를 구함

  4. 같으면 압축율을 증가시키고

  5. 다르면 압축율과 문자를 더해서 압축문자열(result)을 만듬

  6. 비교 할 문자를 구하면서 마지막 문자는 안 붙여지고 팅기므로 for 문 밖에서 마지막 문자를 붙임

  7. 이전에 구했던 압축문자열 길이와 비교해서 더 작은 길이를 저장함

  8. 끝

결과

번호 속도
테스트 1 통과 (0.99ms, 52.4MB)
테스트 2 통과 (2.92ms, 49.9MB)
테스트 3 통과 (1.72ms, 52.7MB)
테스트 4 통과 (0.99ms, 52.1MB)
테스트 5 통과 (0.84ms, 50MB)
테스트 6 통과 (1.03ms, 52.4MB)
테스트 7 통과 (3.49ms, 50.4MB)
테스트 8 통과 (2.49ms, 50.3MB)
테스트 9 통과 (4.46ms, 52.6MB)
테스트 10 통과 (9.25ms, 52.4MB)
테스트 11 통과 (1.25ms, 50.2MB)
테스트 12 통과 (1.28ms, 52.3MB)
테스트 13 통과 (9.63ms, 51.8MB)
테스트 14 통과 (4.35ms, 52.2MB)
테스트 15 통과 (1.31ms, 52.1MB)
테스트 16 통과 (0.85ms, 50.2MB)
테스트 17 통과 (8.91ms, 52.6MB)
테스트 18 통과 (7.70ms, 52.6MB)
테스트 19 통과 (8.63ms, 54.9MB)
테스트 20 통과 (7.89ms, 52.6MB)
테스트 21 통과 (9.99ms, 52.7MB)
테스트 22 통과 (10.63ms, 52.7MB)
테스트 23 통과 (9.68ms, 52.5MB)
테스트 24 통과 (7.89ms, 54.4MB)
테스트 25 통과 (10.43ms, 52.9MB)
테스트 26 통과 (8.17ms, 52.5MB)
테스트 27 통과 (15.60ms, 52.6MB)
테스트 28 통과 (0.88ms, 50.4MB)
  • result에 문자열을 더하지 말고 그냥 문자열 길이를 더하는 방식으로 하면 더 시간을 줄일 수 있음

테스트 케이스

1
2
3
4
5
6
7
8
assertEquals(7, test.solution("aabbaccc"));
assertEquals(9, test.solution("ababcdcdababcdcd"));
assertEquals(8, test.solution("abcabcdede"));
assertEquals(14, test.solution("abcabcabcabcdededededede"));
assertEquals(17, test.solution("xababcdcdababcdcd"));
assertEquals(1, test.solution("a"));
assertEquals(2, test.solution("aaaaa"));
assertEquals(3, test.solution("aaaaaaaaaa"));

참고 사이트