[Programmers] Lv2. 문자열 압축 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

문제에서 주어진 내용대로 구현하면 시간 초과나지 않을까 했는데, 통과되었네요. 문제가 그리 어렵진 않았습니다. 브루트 포스로 풀어도 될 것 같습니다.

 

✏️소스 코드 및 결과

#include <string>
using namespace std;

int solution(string s) {
	int answer = 10000;
	int extractNum = 1;

	while (extractNum <= s.length()) {
		string preToken = "";
		string compressedString = "";
		int repeatCount = 1;

		for (int i = 0; i < s.length(); i += extractNum) {
			string token = s.substr(i, extractNum);

			if (preToken.empty()) {
				preToken = token;
				continue;
			}

			if (preToken != token) {
				string strRepeatCount = repeatCount == 1 ? "" : to_string(repeatCount);
				compressedString += strRepeatCount;
				compressedString += preToken;

				// 최솟값보다 큰 경우는 볼 필요 없으므로 다음 루프로
				if (answer < compressedString.length())
					continue;

				preToken = token;
				repeatCount = 1;
				continue;
			}

			repeatCount++;
		}

		string strRepeatCount = repeatCount == 1 ? "" : to_string(repeatCount);
		compressedString += strRepeatCount;
		compressedString += preToken;
		answer = min(answer, (int)compressedString.length());
		extractNum++;
	}

	return answer;
}