[프로그래머스] 문자열 압축

문제 링크

1. 문제 해결

문제에서 주의해야 할 점은 아래와 같다.

1. 문자열 맨 앞부터 수행하며 압축을 진행한다.
2. 1부터 시작하여 주어진 문자열 길이 / 2 까지 압축길이를 정하여 압축을 진행한다.

1-1. 1부터 시작하여 주어진 문자열 길이 / 2 까지 압축길이를 정하여 압축을 진행한다.

필자는 Map을 이용해서 문자 압축 수를 표시하였다.

알고리즘 순서는 단순하다.

1. 기저 사례
 1-1. 시작 지점(start) + 정해진 길이(len)가 주어진 문자열(s) 보다 큰 경우,
      map에 있는 값을 붙인 후, 시작 지점(start)부터 s의 길이까지 반복하여 남은 문자를 붙인다.

2. 현재 자른 문자열이 Map에 없을 경우.
 2-1. Map에 있는 값을 StringBuilder에 붙이고 map을 clear한 뒤, 현재 자른 문자열을 Map에 넣는다.

3. 현재 자른 문자열이 Map에 있는 경우.
 3-1. 문자열을 Key로 하여 해당 value를 1씩 누적한다.

1-2. 주의 사항

TC 5번이 틀릴 경우, 주어진 문자열의 길이가 1인 경우이다. 주어진 문자열의 길이가 1인 경우, 1을 반환한다.

2. 소스 코드

import java.util.*;
class Solution {
public static int solution(String s) {
		Map<String, Integer> map = new HashMap<>();
if(s.length() == 1)
			return 1;
    
		int ret = Integer.MAX_VALUE;
		for (int len = 1; len <= s.length() / 2; len++) {
			ret = Math.min(ret, divideString(s, 0, len, map, new StringBuilder()));
			map.clear();
		}

		return ret;
	}

	private static int divideString(String s, int start, int len, Map<String, Integer> map, StringBuilder sb) {
		if (start + len > s.length()) {
			sb.append(makeString(map));
			map.clear();
			
			//남은 문자열 처리
			for(int i= start ; i < s.length() ;i++) {
				sb.append(s.charAt(i));
			}
			
			return sb.length();
		}

		
		String sub = s.substring(start, start + len);
		if (map.isEmpty()) {
			// map이 비어있는 경우
			map.putIfAbsent(sub, 1);
		} else {
			if (map.containsKey(sub))
				map.computeIfPresent(sub, (k, v) -> v + 1);
			else {
				sb.append(makeString(map));
				map.clear();
				map.putIfAbsent(sub, 1);
			}
		}

		return divideString(s, start + len, len, map, sb);
	}

	private static String makeString(Map<String, Integer> map) {
		for (Map.Entry<String, Integer> m : map.entrySet()) {
			return m.getValue() != 1 ? m.getValue() + m.getKey() : m.getKey();
		}
		return null;
	}
}