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

링크

https://programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축 | 프로그래머스

풀이

 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 구하는 문제인데.

 

문자열의 길이가 1000 이하로 정해져 있기 때문에 o(n^2)의 시간 복잡도로 풀리는 문제인걸 알 수 있었다.

 

주어진 문자열 전체를 substr 함수를 이용하여 압축하고자 하는 길이만큼 비교하여 압축을 진행하였고

 

압축이 완성되었을 때 길이를 비교하여 결과를 찾아내었습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>

#define SIZE 1010
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

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

	int res = s_size;
	for (int i = 1; i <= s_size / 2; i++) {
		int word_cnt = 1;
		string tmp = "";
		string left, right;
		int j;
		for ( j = i; j < s_size; j+=i) {
			left = s.substr(j - i, i);
			right = s.substr(j, i);

			if (left == right) {
				word_cnt++;
			}
			else if (left != right) {
				if (word_cnt != 1) {
					tmp += to_string(word_cnt);
				}
				tmp += left;
				word_cnt = 1;
			}
		}
		if (word_cnt != 1) {
			tmp += to_string(word_cnt);
			tmp += left;
		}
		else if (word_cnt == 1) {
			tmp += right;
		}

		res = min(res,(int) tmp.size());
	}
	return res;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	string s; cin >> s;

	cout << solution(s);
}