[ 프로그래머스 / String ] 문자열 압축 소스코드

1. 문제

---

 

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

 

2. 소스코드

---

- 꼼꼼히 풀면 쉬운문제. 물론 나는 해맸다.

- 문자열의 최대 길이는 1000이다. 문자열은 최대 절반 길이까지만 압축이 가능하므로, 최대 500회를 비교해야한다. 1번 비교하는데 약 1000회라고 하면, 500 x 1000 = 50만 연산이 필요하다. 이 정도면 단순 for문으로도 널널하게 수행될 것이라 예상함.

- substr을 쓰는게 편했다.

- 압축되는 수 만큼, 숫자를 문자앞에 붙여줘야하는데 ( 예, 5abc ) 이를 처음에 to_string(num)이 아닌 num + '0'으로 변환해서 fail을 받았다.

- 초기화를 잘못해서 fail을 받기도 했다. 처음엔 문자열의 최대길이 1000으로 초기화 했었는데, 입력 문자열이 1인 경우 로직 에러가 발생했다. for문은 len / 2 까지만 탐색하기 때문. 입력 문자열이 1인 경우, len / 2 = 0으로 for문을 돌지 않는다.

 

 

소스코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    
    int len = s.size();
    int answer = len; // 초기화 주의

    for(int cut = 1 ; cut <= len/2; ++cut){
        string conv = "";
        for(int i = 0 ; i < len; ){
            int match = 1;        
            string curString = s.substr(i, cut );
            string nextString = "";
           
            // 다음 문자열이 계속 일치하는 지 확인
            while(i + cut * (match) < len){
               nextString = s.substr(i + cut * match, cut);
               if(curString.compare(nextString) == 0)
                    match++;
               else break;
            }
			
            // 일치하는 문자열이 있었다면 숫자를 붙인다.
            if(match > 1){
                conv += to_string(match);
            }
            conv += curString;
            
            // 일치한 만큼, 인덱스를 넘긴다.
            i+= match * cut;
        }
		// 최소값이면 정답을 갱신한다.
        if(conv.size() < answer) answer = conv.length();
    }
    return answer;
}