[프로그래머스] 문자열 압축 (2020 KAKAO BLIND RECRUITMENT)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60057

 

<전체적인 알고리즘>

문자열 절단 단위를 1,2,3 ..... 증가시켜가며 각각 문자열 길이가 최소인 경우를 찾는다.

 

<세부적인 알고리즘>

1. 원래 문자열을 자를 문자열 절단 단위를 1부터 반절까지 증가시키며 자른다.

2. 문자열 절단 단위(i)가 하나 정해지면 처음붙터 문자열 단위 씩 자르면서 전 문자열과 비교한다.

  2-1  전 문자열과 현재 문자열이 같다면 total_size에서 문자열 절단 단위(i)만큼 뺀다.

  2-2 전 문자열과 현재 문자열이 다르다면  증가시켜온 same_count 정수의 자릿수만큼 total_size에 더한다.

3. 문자열 절단 단위마다 문자열 길이가 최소인 값을 찾는다.

 

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

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

	for (int i = 1; i <= s.size() / 2; i++)  // 총 문자열 크기의 반을 넘어가면 의미가 없음
	{
		int total_size = s.size();
		string pre = "";
		string current = "";
		int same_count = 1;
        
		for (int j = 0; j < s.size(); j++)       
		{
			current += s[j];
			if (current.size() == i)     //문자열크기가 i가되면
			{
				if (current.compare(pre) == 0   //전 문자열과 다음 문자열이 같은경우 
				{
					same_count++;         //같은개수 증가
					total_size -= i;         //총 사이즈 문자열 크기만큼 감소
				}
				else
				{
					string ss = to_string(same_count);   //같은문자열 개수를 나타내는 정수의 문자 수
					                                  //10으로 나누면서 개수세도 됨
                    if(same_count>1)total_size += ss.size();  //정수가 1이하면 숫자없어야함
					
					same_count = 1;
				}
				pre = current;
				current = "";
			}
		}
		if (same_count > 1)
		{
			string ss = to_string(same_count);
			total_size += ss.size();
		}
		result = min(result, total_size);
	}
    
    return result;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.