[C/C++] 프로그래머스스쿨 문자열압축, 구현

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

프로그래머스

코드

#include <string>

using namespace std;

int solution(string s) {
    string cnt_s;
	int sum, check, cnt, a, size = 1, answer = s.length();

	while (size <= s.length() / 2) {
		sum = s.length();
		check = 0;
		cnt = 1;
		a = s.length() - size - s.length() % size;
		for (int i = 0; i < a; i += size) {
			if (s.substr(i, size) == s.substr(i + size, size)) {
				sum -= size;
				cnt++;
				if (check == 0) 
					check = 1;
			}
			else {
				check = 0;
				if (cnt > 1) {
					cnt_s = to_string(cnt);
					sum += cnt_s.size();
				}
				cnt = 1;
			}
		}
		if (cnt > 1) {
			cnt_s = to_string(cnt);
			sum += cnt_s.size();
		}
		if (sum < answer)
			answer = sum;
		size++;
	}
	return answer;
}

풀이

1. 문자열을 자르고자 하는 단위가 size일 때, 무조건 s[0]부터 size만큼 잘라야 한다.

2. 1과 같은 이유로 부분 문자열을 잘라 비교할 때에 인덱스를 무조건 size만큼 증가시켜야 한다.

3. 부분 문자열이 반복된다면 sum=s.length()에서 size만큼 빼준다.

4. check라는 변수를 활용해 부분 문자열이 계속 반복되는지 확인한다.

5. cnt라는 변수를 활용해 부분 문자열이 몇 번 반복되는지 확인한다.

6. 부분 문자열 반복이 끊기고 check가 1이라면 이전 부분 문자열은 반복된 것이므로 cnt를 문자열로 변환하여 cnt_s의 사이즈만큼 sum에 더한다.

7. s의 마지막 문자에 도달하면 중간에 부분 문자열 반복이 끊긴 적이 없었을 경우를 고려해 6번을 다시 실행한다.

 

(*입력이 만약 aaaaaaaaaa (=a가 열 번 반복됨)라면 축약이 10a이므로 1, 0, a이기 때문에 3이어야 한다.)