[프로그래머스] 문자열 압축 C++ 풀이

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

프로그래머스

전체 코드

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

int solution(string s) {
    int answer = 0;
    answer = s.length();

    for (int i = 1; i < s.length(); i++)
    {
        vector<string> v;
        string str;
        for (int j = 0; j < s.length(); j++)
        {
            str += s[j];
            if (str.length() == i)
            {
                v.push_back(str);
                str = "";
            }
            else if (j == s.length() - 1)
                v.push_back(str);
        }

        string res;
        while (v.size() != 0)
        {
            int cnt = 0;

            for (int j = 1; j < v.size(); j++)
            {
                if (v[0] == v[j])
                {
                    cnt++;
                }
                else
                    break;
            }

            if (cnt > 0)
                res += (to_string(cnt + 1) + v[0]);
            else
                res += v[0];
            v.erase(v.begin(), v.begin() + cnt+1);
        }

        answer = min(answer,(int)res.length());
    }

    return answer;
}

 

크게 풀이 방법을 알려드리자면 일단 문자열을 모든 방법으로 잘라보고 각 방법마다 문자열 길이가 어떻게 되는지 비교하여 최소 길이를 찾아낼 겁니다.

 

 

 

int answer = 0;
answer = s.length();

일단 문자열을 전혀 압축을 안 한 것이 문자열의 최대 길이이므로

answer은 기본적으로 가장 긴 문자열은 문자열 s의 길이입니다.

 

 for (int i = 1; i < s.length(); i++)
    {
        vector<string> v;
        string str;
        ...
    }

i는 길이 몇으로 잘라볼것인지에 대한 변수입니다. 사실상 i를 s.length() 까지 할 필요 없이 s.length()/2까지만 하여도 충분합니다.

vector <string> v에는 i의 길이로 잘라진 조각난 문자열들을 담을 것입니다.

str은 조각난 문자열을 만드는 과정에 사용할 것입니다.

 

for (int j = 0; j < s.length(); j++)
{
	str += s[j];
	if (str.length() == i)
	{
		v.push_back(str);
		str = "";
	}
	else if (j == s.length() - 1)
		v.push_back(str);
}

j는 0부터 s의 길이까지 반복하며

str에 s의 j번째 문자를 담습니다.

만약 우리가 조각낼 길이 i만큼 str에 담겼다면 v에 넣어주고 str을 다시 아무것도 없는 상태로 초기화합니다.

이때 길이 i만큼 조각내기도 전에 s의 문자열이 끝나버릴 수 있으니 이때 else if문을 통해 v에 넣어줬습니다.

 

string res;
while (v.size() != 0)
{
	int cnt = 0;

	for (int j = 1; j < v.size(); j++)
	{
		if (v[0] == v[j])
		{
			cnt++;
		}
		else
			break;
	}
            ...
}

이제 조각난 문자열을 이용해 압축할 겁니다.

압축된 내용은 res에 만들 거고 v에 담긴 것이 없을 때까지 반복할 것입니다.

v에 담긴 0번째 문자열을 기준으로 for 반복문을 통해 몇 개가 똑같은지 cnt를 통해 카운트합니다.

 

if (cnt > 0)
	res += (to_string(cnt + 1) + v[0]);
else
	res += v[0];

cnt의 개수가 0보다 크다면 연속적으로 중복된 내용이 있는 것으로 cnt+1개로 압축이 가능하므로

res에 압축한 문자열을 추가해줍니다.

만약, cnt가 0이라면 이것은 압축이 불가능한 것으로 v의 0번째 문자열을 그대로 넣어줍니다.

 

v.erase(v.begin(), v.begin() + cnt+1);

v에 중복된 개수 cnt만큼 v에서 지워버립니다.

왜냐하면 우리는 이미 v[0]번째 문자열에 대해 압축을 하여 res에 넣어줬기 때문입니다.

그래서 이제 필요가 없어졌기에 삭제.

 

answer = min(answer,(int)res.length());

압축한 res의 길이가 answer보다 작다면 이것이 최소 길이이므로 초기화시켜줍니다.

 

이것을 v의 크기가 0이 될 때까지 반복합니다.