(C++) - 프로그래머스(2020 KAKAO BLIND RECRUITMENT) : 문자열 압축

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

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

문자열을 다루는 문제였습니다.

 

 

📕 풀이방법

📔 풀이과정

 1. 자르는 단위를 1 ~ s.size()까지 차례대로 정해서 확인합니다.  1-1. s의 처음 0번 index부터 시작해서 s.size() - 1까지 연속된 단위들의 처음을 string 변수 tmp에 저장합니다.  1-2. 이후 tmp가 연속되는 문자열의 개수를 세줍니다. 연속된 부분이 끝났다면 압축결과에 반영해주기 위해 string 변수 compressed에 연속된 문자열과 그 단위가 나타난 횟수를 string으로 바꿔 더합니다. 이 때 한번도 연속된 적이 없다면 그냥 tmp를 더해줍니다.

 

  1-3. 압축해 만든 문자열의 길이가 기존 길이보다 작다면 그 size는 answer에, 문자열은 ans에 저장해줍니다. 

 

 2. answer를 반환합니다.

 

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
string ans;
int solution(string s) {
    for(int i = 0; i < 1001; i++) ans.push_back('a');
    int answer = 0;
    for(int i = 1; i <= s.size(); i++){ //자르는 단위
        string compressed;
        int cnt = 1;
        
        for(int j = 0; j < s.size(); j += i*cnt){
            string block;
            string tmp = s.substr(j,i); //연속되는 단위비교를 위한 기본 문자
            cnt = 1;

            for(int k = j + i; k < s.size(); k += i){
                string cmp = s.substr(k,i); //이후 연속된 단위 문자열 개수 세주기
                if(tmp == cmp) {
                    block = tmp;
                    cnt++;
                }
                else break;
            }

            if(!block.size()) compressed += tmp; //한번도 같은적이 없었다면 바로 추가

            else{
                compressed += block;
                if(cnt >= 2) compressed += to_string(cnt); //2번 이상 연속으로 나왔다면 숫자도 추가.
            }
        }

        if(ans.size() > compressed.size()){
            ans = compressed;
            answer = compressed.size();
        }
    }
    
    return answer;
}