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

✔️ 문제

• 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60057
• 2019 카카오 개발자 겨울 인턴 코딩 테스트 기출문제

✔️ 풀이

• 문제 설명대로 주어진 문자열에 대하여 n개 단위로 압축을 진행했을때, 압축 가능한 가장 짧은 길이를 반환하면 되는 문제다.
• 주어진 문자열이 helloword 라고 한다면, 문자열의 길이는 9다. 이 문자열을 1부터 4(9/2)개 단위로 잘라본다.
• 잘라보면서 문자열 압축을 진행하고, 압축시 가장 짧은 길이를 저장해뒀다가 반환한다.

👨🏻‍💻 소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

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

	for (int i = 1; i <= s.size(); i++) { // i는 자르는 단위이다. 1개씩 자르는 것부터 시작한다.

		string ret = "";
		string tmp = s.substr(0, i); // 제일 첫번째 조각을 자른다.
		int cnt = 1; // 같은 조각을 카운트 하는 변수다.

		for (int j = i; j <= s.size(); j += i) { // substr을 활용하여 i개씩 자른다.

			if (tmp == s.substr(j, i)) { // 앞에서 자른 조각과 같다면, 카운트를 증가한다.
				cnt++;
			}
			else { // 앞에서 자른 조각과 다르다면, 이전에 진행했던 압축 결과를 ret에 저장한다.
				if (cnt > 1)
					ret += to_string(cnt) + tmp;
				else
					ret += tmp;

				tmp = s.substr(j, i);
				cnt = 1;
			}
		}

		// 마지막 조각은 for문안에서 처리되지 못함으로 마지막 조각을 따로 처리해준다.
		// 참고로 substr(index, size)에서 size가 문자열의 크기를 넘어선다면, index부터 끝까지 잘라서 반환한다.
		if (cnt > 1) 
			ret += to_string(cnt) + tmp;
		else
			ret += tmp;

		answer = min(answer, (int)ret.size()); // 압축한 문자열의 길이가 최소값인지 체크한다.
	}

	return answer;
}

✔️ 문제 회고

• substr을 활용할 수 있어야 풀 수 있는 문제다.
• ab 조각이 n번 반복되면 “nab”가 되도록 구현해야한다.