프로그래머스 문자열 압축 (C++)

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

코딩테스트 연습 - 문자열 압축

이 문제는 해석을 대충하다간 틀리기 쉬운 문제이다.

 

문제의 유의사항은 다음과 같다.

1. 1,2,3.. 여러사이즈로 문자열을 자를 수 있는게 아니라 '한 가지 숫자'로 자를 수 있다.

2. 결과로 문자열을 출력하는 것이 아닌, 문자열의 '사이즈'를 출력하는 것이다.

3. 무조건 문자열의 첫 번째 자리부터 자를 수 있다. 때문에 아래와 같은 예시는 어떻게해도 압축이 불가능하다.

xabababababababab

 

문제 풀이는 다음과 같다.

1. 정답 answer 변수는 문자열의 사이즈로 먼저 저장해둔다.

2. 1부터 문자열의 사이즈 / 2 이하까지 for문을 돌린다.

이는 문자를 최대한으로 자를 수 있는 사이즈가 1부터 문자열의 사이즈/2이기 때문이다.

3. 아래 코드를 확인해보자.

    for(int i=1; i<=s.size()/2; i++){
        int cnt = 1;
        string temp = "", a = "";
        a = s.substr(0,i);
        for(int j=i; j<s.size(); j+=i){
            if(a==s.substr(j,i)) cnt++;
            else{
                if(cnt>1) temp+= to_string(cnt);
                temp += a;
                a=s.substr(j,i);
                cnt = 1;
            }
        }

0번째부터 i번째까지 압축한 문자열을 a라고 하고, i번째부터 +i번째까지 문자열을 b라고 가정하자. (참고로 위의 코드에서 b라고 별도의 함수를 만들지는 않았다.)

a와 b가 같을 경우 cnt의 수를 +1해준다.

그렇지 않을 경우 압축이 불가능하다는 의미로, cnt를 문자열로 바꾸어 일시 저장값 temp에 넣어준다.

이제부터는 범위를 바꾸어, b를 a에 저장해주고 새로이 바뀐 a값을 기준으로 다시 비교를 시작해나간다.

4. 아래 코드를 확인해보자.

        if(cnt>1) temp+=to_string(cnt);
        temp+=a;
        if(answer>temp.size()) answer = temp.size();

i사이즈만큼 비교를 모두 끝냈을 경우, 만약 남은 문자열이 있는 경우를 생각해보자.

cnt>1이라면 cnt를 문자열로 저장해줘서 temp에 저장해주고, 남은 문자열인 a를 그대로 temp에 저장해준다.

만약 i의 길이가 문자열의 사이즈에 딱 맞아 떨어져서 미쳐 계산하지 못한 남은 문자열이 없을 경우, "" = 공백이 더해져서 별 다른 이상이 없을 것이다.

5. 이렇게 계산한 temp의 사이즈가 answer보다 작을 경우, answer에 temp의 사이즈를 저장해준다.

 

#include <string>

using namespace std;

int solution(string s) {
    int answer = s.size();
    for(int i=1; i<=s.size()/2; i++){
        int cnt = 1;
        string temp = "", a = "";
        a = s.substr(0,i);
        for(int j=i; j<s.size(); j+=i){
            if(a==s.substr(j,i)) cnt++;
            else{
                if(cnt>1) temp+= to_string(cnt);
                temp += a;
                a=s.substr(j,i);
                cnt = 1;
            }
        }
        if(cnt>1) temp+=to_string(cnt);
        temp+=a;
        if(answer>temp.size()) answer = temp.size();
    }
    return answer;
}