압축(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

현재 입력과 일치하는 가장 긴 단어의 색인 번호를 출력하고, 현재 입력에 다음 글자 하나를 더해 사전에 추가한다.

 

---

 

풀이

 

접근 방식

1. 크기가 1인 단어들로 사전 초기화

  → char 타입의 변수에 'A'를 저장 후 'Z'까지 ++ 해가며 map에 담는다.

 

2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 찾기

  → 주어진 문자열 msg의 길이부터 하나씩 줄여가며 사전에서 일치하는 단어 찾기(완전 탐색)

 

3. 사전에서 일치하는 가장 긴 문자열을 자르고 난 후 남은 msg의 길이 확인

  → 0인 경우 while문 탈출

  → 1인 경우 map.get(msg)를 통해 찾은 value를 list에 담고 while문 탈출

  → 2 이상인 경우 msg의 첫 번째 문자를 잘라서 현재 입력과 합친 후 사전에 저장

 

---

 

코드리뷰

 

import java.util.*;

public class Solution {
    public int[] solution(String msg) {
        HashMap<String, Integer> map = new LinkedHashMap<>();
        char chr = 'A';
        int chrInt = 1;	// 색인 번호

        while(true) {	// 크기 1인 단어들로 사전 초기화
            map.put(String.valueOf(chr), chrInt);
            chr++;	// 'A' 담고 ++ 해가며 'Z'까지 담기
            chrInt++;	// 색인 번호도 함께 ++
            if(String.valueOf(chr).equals("Z")) {
                map.put(String.valueOf(chr), chrInt);
                chrInt++;	// 다음 단어의 색인 번호를 위해 ++ 실행
                break;
            }
        }
        
        List<Integer> list = new ArrayList<>();
        boolean run = true;	// while-for 이중 loop 탈출을 위한 변수 run
        while(run) {
            for(int i = msg.length(); i > 0; i--) {	// 가장 긴 문자열 부터 하나씩 확인(완전탐색)
                String w = msg.substring(0, i);	// ex) msg = "KAKAO"의 경우, KAKAO, KAKA, KAK, KA, K 순으로 사전에서 확인
                if(map.keySet().contains(w)) {	// 현재 입력(w)이 사전에 있다면
                    list.add(map.get(w));	// 색인 번호 list에 담기
                    msg = msg.substring(i);	// 현재 입력(w)을 제외한 나머지
                    if(msg.length() == 0) {
                        run = false;	// 길이가 0인 경우 while문 탈출
                        break;
                    } else if(msg.length() == 1) {
                        list.add(map.get(msg));	// 길이가 1인 경우 msg 자체를 key값 삼아 value 찾고 while문 탈출
                        run = false;
                        break;
                    } else {
                        String c = msg.substring(0, 1);	// 길이가 2 이상인 경우 현재 입력(w)과 다음 글자(c) 합친 후 사전에 등록
                        map.put(w+c, chrInt);
                        chrInt++;
                        break; // if-else if-esle문 모두 for문 탈출 break 포함(현재 입력(w)이 사전에 있다는 전제 조건 때문)
                    }
                }
            }
        }
        int[] answer = new int[list.size()];
        for(int i = 0; i < answer.length; i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}