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

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

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

 

 

 

알고리즘 종류

    - 문자열

 

 

 

사고 과정

    1. 자를 길이를 결정한다.

    2. 초기에 맨 앞에서부터 자른다.

    3. 잘라진 문자열(str)과 이후 잘라진 문자열(str2)을 비교한다.

        3-1. 비교 후, 같으면 cnt++

        3-2. 비교 후, 다르면 임시 tmp에 cnt + str를 저장한다.

        3-3. cnt, str 변수를 초기화 한다.

    4. 끝에 남은 문자열을 처리한다.

    5. 길이를 비교하여 갱신한다.

 

 

 

구현(C++)

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
int solution(string s) {
    // 최대 길이 설정 
    int answer = s.size();
    
    for(int len=1; len <= s.size()/2; len++){
        
        int cnt=1; // 압축된 개수
        int idx=0; // 문자열에서 index
        string tmp = ""; // 압축된 문자열 저장 
        string str = s.substr(0, len); // len 단위로 잘라진 시작 문자열
        
        // len 만큼 이동
        for(idx=len; idx<s.size(); idx+=len){
            string str2 = s.substr(idx, len);
            
            if(str == str2) cnt++; // 이전에 잘라낸 문자열와 같으면 갯수 증가
            else{
                // 이전에 잘라낸 문자열과 다르면 tmp에 추가하기
                if(cnt==1) tmp += str;
                else tmp += to_string(cnt) + str;
                // 그리고 str을 변경하고, cnt 초기화 
                str = str2;
                cnt=1;
            }
        }
        
        // 마지막에 남은 문자열 처리하기
        if(cnt==1) tmp +=  str;
        else tmp += to_string(cnt) + str;
        
        if(tmp.size() < answer) answer = tmp.size();
    }
    
    return answer;
}

 

 

 

시행착오

    - 자를 길이를 설정할 때에 입력된 문자열 s 길이의 반만 하면 된다는 것을 다른 분의 해설을 보고 알 수 있었다. 생각해보면, s의 길이 반 이상부터는 무조건 최대길이가 나온다. 중복되는 문자열이 생성되지 않기 때문이다. 너무 기본적인 내용이지만 본인은 생각하지 못했다. '속도를 향상시키는 방법' 또는 '불필요한 처리'를 생각하면서 프로그램을 작성하자.

 

    - 최대 길이가 입력된 s 길이라고 생각을 하지 않았다. 평소처럼 987654321로 설정했다. 이것도 기본적인 내용이다. 어떻게 압축하던지 최대 길이는 입력된 s 길이가 되는 것은 당연하다. 변수 초기화에서 대충 설정하지 말자.