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

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

프로그래머스

<풀이>

1. 주어진 문자열 맨 앞에서 부터 한 글자, 두 글자씩 잘라보면서 가장 짧게 압축된 문자열의 길이를 출력한다.

​

<해법>

1. 문자열을 압축하는 방법

=> 코딩으로 문자열을 압축하는 방법을 생각하기 이전에, 사람은 어떤 방법으로 문자열을 압축하는지 생각해보았습니다. 그 이후 사람이 압축하는 방법을 도식화 시켜 코드로 구현하였습니다.

​

① 사람이 문자열을 압축하는 방법

② 도식화

#include <iostream>
#include <string>
using namespace std;
 
int solution(string s) {
 
    int answer = 1;
 
    //주어진 문자열 길이
    int sLength = s.length();
 
    //1칸,2칸 ... 길이의 절반만큼 문자 자르기 반복
    for (int i = 1; i <= sLength / 2; i++) {
 
        //최종 문자열 보관
        string tmp = "";
 
        //처음 비교 문자열, 반복된 갯수
        string cmp = s.substr(0, i);
        int cnt = 1;
 
        //문자열 처음부터 끝까지 시행
        for (int j = i; j <= sLength; j += i) {
 
            //현재 문자열
            string cur = s.substr(j, i);
 
            //현재 문자열과 비교 문자열과 비교
            //현재 문자열과 비교 문자열이 같다면
            if (cmp == cur) {
                cnt++;
            }
            //현재 문자열과 비교 문자열이 다르다면
            else {
                //이전에 반복된 문자열이 있다면 반복된 문자열 출력
                if (cnt > 1) {
                    tmp += (to_string(cnt) + cmp);
                    cnt = 1;
                }
                else {
                    tmp += cmp;
                }
                cmp = cur;
            }
        }
 
        //문자열 뒤에 남은 문자들
        if (sLength / i != 0) {
            tmp += s.substr((sLength / i) * i);
        }
 
        //결과 저장
        if (answer == 1 || tmp.length() < answer) {
            answer = tmp.length();
        }
    }
 
    return answer;
}

 

문자열과 구현에 대해 알아볼 수 있는 문제였습니다.