문제

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

코드

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
60
61
62
63
64
65
66
67
68
private static final int CAPITAL_A = 65;
private static final Character LAST_INIT_ALPHABET = 'Z';

public int[] solution(String msg) {
    int[] answer = getDictionaryIndex(msg.toCharArray(), initIndexMap());

    return answer;
}

private Map<String, Integer> initIndexMap() {
    Map<String, Integer> indexMap = new HashMap<>();

    Character start = CAPITAL_A;
    int i = 1;

    while (start <= LAST_INIT_ALPHABET) {

        indexMap.put(String.valueOf(start), i);

        ++start;
        ++i;
    }

    return indexMap;
}

private int[] getDictionaryIndex(char[] charArray, Map<String, Integer> indexMap) {
    int i = 0;
    int arrayLength = charArray.length;
    int lastIndex = indexMap.get(String.valueOf(LAST_INIT_ALPHABET));

    List<Integer> answer = new ArrayList<>();

    while (i < arrayLength) {
        StringBuilder sb = new StringBuilder();

        int value = 0;
        int jump = 0;
        for (int j = i; j < arrayLength; j++) {
            sb.append(charArray[j]);

            String key = sb.toString();
            if (indexMap.containsKey(key)) {
                value = indexMap.get(key);
                jump++;

                if (j +1 == arrayLength) {
                    answer.add(value);
                    i += jump;
                }

                continue;
            }

            answer.add(value);
            i += jump;
            break;
        }

        if (!indexMap.containsKey(sb.toString())) {
            indexMap.put(sb.toString(), ++lastIndex);
        }

        sb.setLength(0);
    }

    return answer.stream().mapToInt(index -> index).toArray();
}

흐름

  1. A부터 Z를 Key로 하는 Map을 만든다.
  2. 압축 할 문자열의 길이만큼 반복한다.
  3. 돌면서 현재 문자가 Map에 key에 포함되는지 확인한다.
  4. 이미 포함되어 있으면(처음엔 A~Z) 해당 문자의 index를 뽑아내기 위해 value를 꺼내서 저장한다.
  5. 이번 문자는 포함되어 있으므로 그 다음 문자열의 index까지 점프하기 위해 jump 변수를 증가시킨다.
  6. 현재 문자가 문자열의 마지막 문자라면 더 이상 사전에서 검색 할 수 없으므로,
  7. 문자열의 index 즉, value를 List에 저장하고 i를 jump 만큼 더해서 문자열의 index를 증가시킨다.
  8. 이미 사전에 있는 문자이므로 continue해서 끝내지 않고 반복문을 올라가서 문자를 더한다.
    1. A가 포함되어 있으면 A 뒤문자인 B를 더해서 AB가 존재하는지 찾기 위해
  9. 사전에 포함되어 있지 않는다면(Map에 key로 존재하지 않는다면)
  10. 이전에 검색했던 문자의 index를 저장하고 i를 jump 시킨 후 반복문을 벗어난다.
  11. 그 후 사전에 존재 하지 않았던 문자를 사전에 등록, Map에 key, lastIndex에서 + 1해서 Map에 추가하고, 문자를 저장했던 StringBuilder를 초기화 시킨다.
  12. 문자열 모두 검색 할 때까지 반복한다.
  13. 사전에서 검색한 index를 저장한 List를 array로 변경한 후 return 한다.
  14. 끝.

결과

번호 속도
테스트 1 통과 (6.64ms, 53MB)
테스트 2 통과 (6.30ms, 52.9MB)
테스트 3 통과 (5.29ms, 50.3MB)
테스트 4 통과 (9.62ms, 53MB)
테스트 5 통과 (5.94ms, 51.1MB)
테스트 6 통과 (10.26ms, 52.8MB)
테스트 7 통과 (7.65ms, 51MB)
테스트 8 통과 (8.38ms, 52.8MB)
테스트 9 통과 (6.01ms, 52.5MB)
테스트 10 통과 (11.33ms, 53MB)
테스트 11 통과 (8.25ms, 51.6MB)
테스트 12 통과 (8.79ms, 51.3MB)
테스트 13 통과 (9.26ms, 53.6MB)
테스트 14 통과 (9.22ms, 51.5MB)
테스트 15 통과 (10.26ms, 53MB)
테스트 16 통과 (8.91ms, 53.5MB)
테스트 17 통과 (10.89ms, 53.2MB)
테스트 18 통과 (7.93ms, 53.2MB)
테스트 19 통과 (8.32ms, 53.1MB)
테스트 20 통과 (8.10ms, 50.8MB)

테스트 케이스

1
2
3
4
assertArrayEquals(new int[] {11, 1, 27, 15}, test.solution("KAKAO"));
assertArrayEquals(new int[] {20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34}, test.solution("TOBEORNOTTOBEORTOBEORNOT"));
assertArrayEquals(new int[] {1, 2, 27, 29, 28, 31, 30}, test.solution("ABABABABABABABAB"));
assertArrayEquals(new int[] {20, 8, 1, 20, 27, 29, 9, 19, 33, 31, 30, 28, 20, 33, 14, 15, 39, 19, 41, 43, 36, 9, 39, 46, 38, 47, 34, 19, 36, 52, 45, 40, 42, 35, 38, 48, 62, 54, 51, 61, 53, 55, 66, 57, 44, 59, 64, 32, 49, 60, 29, 52, 76, 37, 32, 71, 43, 70, 47, 75, 73, 80, 43, 79, 56, 72, 84, 61, 86, 68, 81, 90, 69, 92, 72, 85, 63, 96, 89, 87, 91, 83, 101, 94, 103, 65, 97, 106, 99, 108, 50, 74, 111, 77, 66, 98, 81, 70, 93, 118, 117, 88, 33, 122, 116, 58, 127, 62, 127, 78, 114, 123, 100, 133, 95, 112, 105, 104, 132, 145, 87, 134, 130, 129, 137, 131, 82, 79, 148, 151, 150, 144, 153, 159, 102, 135, 121, 156, 159, 125, 75, 162, 113, 158, 124, 109, 126, 149, 67, 142, 146, 166, 155, 158, 174, 171, 140, 119, 128, 175, 120, 138, 152, 161, 174, 181, 139, 154, 141, 187, 143, 176, 165, 172, 167, 191, 164, 182, 194, 184, 136, 170, 193, 147, 86}, test.solution("THATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITISTHATTHATISISTHATTHATISNOTISNOTISTHATITITIS"));

여담

  • 코드의 퀄리티가 썩 마음에 들지 않는다.
  • 시간 날 때 리팩토링을 꼭 해야 할 듯 싶다.