프로그래머스 - 17684번: [3차] 압축 [Java]

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

프로그래머스

1. 코드

import java.util.*;
class Solution {
    public List<Integer> solution(String msg) {
        List <Integer> list = new ArrayList<>();
        Map <String, Integer> map = new HashMap<>();
        int index = 1;
        for(char c = 'A'; c <= 'Z'; c++)
            map.put(String.valueOf(c), index++);
        
        int len = 0;
        for(int i = 0; i < msg.length(); i = len - 1) {
        	boolean check = false;
            for(int j = i + 1; j <= msg.length(); j++) {
            	len = j;
                if(!map.containsKey(msg.substring(i, j))) {
                	check = true;
                	break;
                }
            }
            if(!check)
            	list.add(map.get(msg.substring(i, len)));
            else
            	list.add(map.get(msg.substring(i, len - 1)));
            map.put(msg.substring(i, len), index++);
            
            if(len == msg.length() && !check)
            	break;
        }
        return list;
    }
}

2. 설명

List <Integer> list = new ArrayList<>();
Map <String, Integer> map = new HashMap<>();
int index = 1;
for(char c = 'A'; c <= 'Z'; c++)
    map.put(String.valueOf(c), index++);

우선 HashMap에 'A'부터 'Z'까지 1부터 순서대로 저장합니다.

int len = 0;
for(int i = 0; i < msg.length(); i = len - 1) {
    boolean check = false;
    for(int j = i + 1; j <= msg.length(); j++) {
        len = j;
        if(!map.containsKey(msg.substring(i, j))) {
            check = true;
            break;
        }
    }

반복분을 통해서 HashMap에 이미 저장된 문장여부를 확인하여 문자열의 길이를 늘려가는데 만약 HashMap에 존재하지 않으면 check를 통해서 존재여부를 알려줍니다. 그리고 반복문을 중지합니다.

    if(!check)
        list.add(map.get(msg.substring(i, len)));
    else
        list.add(map.get(msg.substring(i, len - 1)));
    map.put(msg.substring(i, len), index++);

    if(len == msg.length() && !check)
        break;
}
return list;

만약 찾지 못했다면 i부터 len까지의 길이의 msg 문자열을 사전에서 찾아 List에 저장합니다. 아니라면 i부터 len - 1까지의 길이를 저장합니다. Map에는 이미 저장된 순서대로 저장합니다.

만약 len의 길이가 msg의 길이와 동일한데 Map에 문자열이 존재하지 않는다면 마지막을 의미하기에 반복문을 종료한 뒤 list를 반환하면 됩니다.

3. 정리

1. 마지막 확인 여부만 신경쓰면 쉽게 해결 가능하다.
2. List와 Map을 적절히 활용하자.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges