[Java] 프로그래머스 60057.문자열압축 (Lv.2)

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

코딩테스트 연습 - 문자열 압축

 

지문이 한 번에 이해가 되지 않아 여러 번 읽어본 문자열 압축 문제입니다. 문제를 이해하면 구현하는것은 크게 어렵지 않지만, 고려해야할 상황이 두 개 있습니다.

 

1. 문자열이 압축되는 경우 중복된 문자열은 생략되고 중복갯수를 더해주어야 합니다.

2. 압축된 문자열의 갯수가 10,100처럼 한 자리가 아닌 여러 자릿수인 경우를 고려해야합니다.

 

저는 중복이 가능한 문자열의 모든 길이 (1 ~ 문자열의 총 길이/2)를 순회하며 문자열의 중복을 체크하고, 이 체크 갯수를 카운팅 한 뒤 중복이 끝나는 경우 갯수에 따라 길이를 늘려주는 식으로 구현했습니다.

문자열이 아닌 문자열의 길이가 필요한 정답이기에 문자열 대신 숫자만 카운트했습니다.

 

public class q60057_Programmers_문자열압축 {
	public static void main(String[] args) {
		String[] strArr = { "aabbaccc", "ababcdcdababcdcd", "abcabcdede", "abcabcabcabcdededededede",
				"xababcdcdababcdcd",  "aaaaaaaaaaaabcd", "xxxxxxxxxxyyy"};
		
		for (int i = 0; i < strArr.length; i++) {
			System.out.println(solution(strArr[i]));
		}
//		System.out.println(solution(strArr[5]));
	}

	private static int solution(String s) {
		char[] strArr = s.toCharArray();
		int answer = strArr.length;

		for (int i = 1; i <= strArr.length / 2; i++) {
			int count = i;
			int idx = 0;
			int now = i;
			int duple = 0;
			for (; now < strArr.length - (strArr.length % i); now += i) {
				boolean flag = true;
				for (int j = 0; j < i; j++) {
					if (strArr[idx + j] != strArr[now + j]) {
						flag = false;
						break;
					}
				}
				if (flag) {
					duple = (duple == 0) ? 2 : ++duple;
				} else {
					idx = now;

					if (duple / 100 != 0) {
						count += 3;
					} else if (duple / 10 != 0) {
						count += 2;
					} else if (duple != 0) {
						count++;
					} 
					count += i;
					duple = 0;
				}
			}
			if (duple / 100 != 0) {
				count += 3;
			} else if (duple / 10 != 0) {
				count += 2;
			} else if (duple != 0) {
				count++;
			} 
			duple = 0;
			answer = Math.min(answer, count + (strArr.length % i));
		}

		return answer;
	}
}