문자열 압축

문제 링크 => 코딩테스트 연습 - 문자열 압축 | 프로그래머스 (programmers.co.kr)

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

---

문자열을 압축하는 과정은 다음과 같다.

 

예시로 문자열이 "xxxabcabcdede" 가 있다고 가정하자.

 

(1) 문자열을 1개 단위로 자르는 경우 => x / x / x / a / b / c / a / b / c / d / e / d / e 

이때 "x" 가 연속으로 3개 있으므로 "3x" 으로 치환이 가능하고 나머지는 연속으로 되어 있지 않으므로 그대로 써야 한다. 

따라서 압축한 결과는 3xabcabcdede 이다.

 

(2) 문자열을 2개 단위로 자르는 경우 => xx / xa / bc / ab / cd / ed / e 

이 경우는 연속으로 되어 있는 경우가 없으므로 압축할 수 없다.

 

(3) 문자열을 3개 단위로 자르는 경우 => xxx / abc / abc / ded / e

이 경우는 "abc" 가 연속으로 2개 있으므로 "2abc" 로 치환이 가능하고 나머지는 연속으로 되어 있지 않으므로 그대로 써야 한다.

따라서 압축한 결과는 xxx2abcdede 이다.

 

...

...

 

(6) 문자열을 6개 단위로 자르는 경우 => xxxabc / abcded / e

이 경우는 연속으로 되어 있는 경우가 없으므로 압축할 수 없다.

 

여기서 핵심은 a개 단위로 자를 때, a = s.size() / 2 이여야 한다.

 

예를들어 위 문자열의 경우 7개 단위로 자르는 경우 xxxabca / bcdede 인데 압축할 수 없으므로 그 이상은 무시해도 된다.

 

따라서 (1) ~ (6) 에서 압축한 문자열들의 길이 중에 가장 작은 값이 정답이다.

 

풀이 Code

 

c++

닫기 줄바꿈

#include <string>
#include <vector>

using namespace std;

string S;

string getString(int left, int right) {
	string ret = "";
	for (int i = left; i < right; i++) ret += S[i];
	return ret;
}

int min(int x, int y) {
	if (x > y) return y;
	return x;
}

int solution(string s) {
	int answer = s.size();
	S = s;

	for (int i = 1; i <= s.size() / 2; i++) {
		int cnt = 1, x;
		string cmp1 = getString(0, i), res = "";

		for (x = i; x < s.size(); x++) {
			if (x + i > s.size()) break;

			string cmp2 = getString(x, x + i);

			if (cmp1 == cmp2) {
				cnt += 1;
				x += (i - 1);
			}
			else {
				if (cnt > 1) res += to_string(cnt) + cmp1;
				else res += cmp1;
				cnt = 1;
				cmp1 = getString(x, x + i);
				x += (i - 1);
			}
		}

		if (cnt > 1) {
			res += to_string(cnt) + cmp1;
			for (int i = x; i < s.size(); i++) res += s[i];
		}
		else {
			res += cmp1;
			for (int i = x; i < s.size(); i++) res += s[i];
		}

		answer = min(answer, res.size());
	}

	return answer;
}