프로그래머스 문자열 압축

문자열 압축 https://programmers.co.kr/learn/courses/30/lessons/60057

 

문제 설명
데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.
예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.
압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

 

너무 복잡하게 생각해서 복잡한 코드로 쓰다가 도중에 뒤죽박죽 되어 지우고 다시 풀기를 두세번 한 뒤에...
문자열을 단위별로 비교하는 부분에서 다른 사람의 풀이를 살짝 보고 다시 정리하여 풀어봤다. 
처음부터 비교할 문자열 before을 잘라놓고, 다음 인덱스 부터 잘라 next와 비교하는 것이다. 
before가 바뀌는 경우는 next와 달라졌을 때만 이다. 

그래도 몇가지 케이스에서 오답이 나자 몇가지 개념이 내가 이해한 것과 다르다는 것을 깨달았다. 

먼저 압축할 글자 단위가 1보다 크거나 같고 length/2와 작거나 같은 크기를 가져야 한다.

또한 받은 문자열 전체가 한 단위로 할 때를 먼저 min값에 넣고 비교해줘야 한다.
처음에 저 값이 1단위로 압축했을 때라고 생각하고 풀어서 입출력 예#1 을 틀렸었다. 

그리고 before와 next를 비교해주는 for문을 나온 후에 처리가 또 필요하다.
마지막 next는 before와 비교만 된 후, cnt증가나 before가 더해지는 경우만 발생했음으로, 
for문 밖에서 answer 에 next를 더하거나 cnt가 2 이상일 경우엔 숫자와 함꼐 더해줘야 한다. 

 

package level2;
//https://programmers.co.kr/learn/courses/30/lessons/60057
public class kakao_string_zip {

	public static void main(String[] args) {
		String s="ababcdcdababcdcd";
		String answer;

		String before, next = null;
		int cnt;
		int min = s.length();//전체를 한 단위로 압축할 때

		for(int unit=1; unit<=s.length()/2; unit++) {//단위는 1~길이의 1/2과 같거나 작아야 한다.
		//int unit = 3;

			answer = "";
			cnt = 1;
			before = s.substring(0, unit);
			for(int i=unit; i<s.length(); i += unit) {

				int start = i;
				int end = i+unit > s.length() ? s.length() : i+unit;
				next = s.substring(start, end);

				if(before.equals(next)){
					cnt ++;

				}else {//다르면 기준을 바꿔주고 cnt 초기화
					if(cnt>=2) {answer += (cnt + before);}
					else {answer += before;}

					before = next;
					cnt =1;
				}

			}

			//위 for 문에서는 마지막 비교한 next가 answer에 더해지지 않은 채 끝났다. 같았을 경우엔 cnt만 하나 증가 한 채로 끝난것.
				if(cnt>=2) {answer += (cnt + before);}
				else {answer += before;}



			min = min > answer.length() ? answer.length() : min;

			}

		System.out.print(min);
	}
}

 

음.. 아마 짚고 넘어가야 할 부분이 있다면 

subString(start, end)에서 end가 문자열 길이보다 크게 되면 오류가 나기 때문에 아래와 같이 해주었다. 

int end = i+unit > s.length() ? s.length() : i+unit;