[3차] 압축 - 2018 KAKAO (Java, Level 2)

처음 풀이

 

1. 사전 생성 후 알파벳 등록

- Map<String, Integer>에 기본 알파벳을 값과 함께 저장
- 뒤로 새로운 문자열 나오면 계속 추가

//사전
Map<String, Integer> dictionary = new HashMap<>();

for (int i = 65; i < 91; i++) {
    dictionary.put((char)(i)+"", i-64);
}//for end

 

2. 문자열 탐색

- 색인값을 추출하지 않은 인덱스서부터 탐색

 

- 간격을 하나씩 벌리면서 주어진 문자열을 자른 후 사전에 있는지 확인

 

- 자른 문자열이 사전에 없으면, 직전 간격으로 자른 문자열의 색인 번호를 출력,

  현재 자른 문자열을 사전에 등록,

  현재 자른 문자열에 포함되지 않은 문자로 인덱스를 이동

 

- 간격을 벌리다가 만일 문자열 인덱스를 넘어가면, (try~catch)

  현재 인덱스서부터 마지막 인덱스까지 자른 문자열의 색인 번호 출력,

  인덱스 이동

 

//색인 번호 저장 리스트
List<Integer> answerList = new ArrayList<>();

int index = 0;
int msgLength = msg.length();

while(index < msgLength) {

    for (int k = 1; k <= msgLength; k++) {
        try {
            //인덱스 범위 벗어나면 발생하는 exception 잡아서 catch 구문 실행
            String subStr = msg.substring(index, index + k+1);

            if (!dictionary.containsKey(subStr)) {
                //색인 번호 출력
                answerList.add(dictionary.get(msg.substring(index, index + k)));
                //사전 등록
                dictionary.put(subStr, dictionary.size() + 1);
                //인덱스 이동
                index += k;
                //for 탈출
                break;
            }//if end
        } catch (Exception e) {
            //인덱스 범위 벗어났으면
            //현재 인덱스서부터 끝까지의 문자열의 색인 번호 출력
            answerList.add(dictionary.get(msg.substring(index)));
            //인덱스 이동
            index += k;
            //for 탈출 
            break;
        }
    }//for end
}//while end

int[] answer = new int[answerList.size()];

for (int i = 0; i < answer.length; i++) {
    answer[i] = answerList.get(i);
}//for end

return answer;

 

 

* 사전을 Map이 아니라 List(ArrayList)로 구현하여 index+1을 값으로 사용하는 방법도 있다.