[programmers] Lv.2 문자열 압축(c++)

#include <string>
#include <vector>

using namespace std;

vector<string> tokenizing(string s, int N){
    vector<string> tokens;
    for(int j=0; s.length()>=N; j+N){
        tokens.push_back(s.substr(j, N));
        s = s.substr(j+N);
        if (s.length()<N) tokens.push_back(s);
    }
    return tokens;
}

int solution(string s) {
    int answer = s.length();
    
    for(int i=s.length()/2; i != 0; i--){
        vector<string> tok = tokenizing(s, i);
        string bf_t = tok[0], cur_t, zip;
        int cnt=0;
        for(int j=1; j<tok.size(); j++){
            cur_t = tok[j];
            if (bf_t == cur_t){
                cnt++;
            }else{
                if(cnt != 0) zip += to_string(cnt+1);
                zip += bf_t;
                cnt = 0;
            }           
            if(j+1 == tok.size()){
                if(cnt != 0) zip += to_string(cnt+1);
                zip += cur_t;
            }
            bf_t = cur_t;
        }
        if(answer >= zip.length()) answer = zip.length();
    }
    
    return answer;
}

---

문제 정리:

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

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

input

• string s : 압축하려는 문자열

output

• 압축한문자열의 최소 길이(int)

- aabbaccc => 2a2ba3c

- 1번 반복된것은 표현하지 않음

- 처음 자른 단어의 길이만큼 잘라야함

- 맨 마지막에 자른것은 정해진 길이보다 작을 수 있음 (딱 떨어지지 않아도 됨)

제한사항

- 1<= len(s) <= 1000

- s 는 알파벳 소문자로만 이루어짐

728x90

---

[접근]

"길이를 하나씩 줄여서 하면... 엄청 오래 걸릴듯. 그래도 일단 해보자"

라는 생각을 했다. 그런데 이게 최선인듯? 다들 이렇게 푼거같다.

---

[접근 1]

정한 숫자로 쪼개는 함수를 만들었다.

string.substr 사용

substr(N): index N부터 끝까지

substr(N, M): index N부터 길이 M만큼 (이상하다.. 난 N부터 M까지 인줄 알고, s.substr(j, j+N)을 했는데 잘 됐다.. 왜지?)

vector<string> tokenizing(string s, int N){
    vector<string> tokens;
    for(int j=0; s.length()>=N; j+N){
        tokens.push_back(s.substr(j, N));
        s = s.substr(j+N);
        if (s.length()<N) tokens.push_back(s);
    }
    return tokens;
}

---

[접근 2]

s 길이의 반 이상으로 쪼개는건 의미가 없다. 어차피 반복되는것이 없을것이기 때문 => i=s.length()/2

bf_t에 tok의 0번째 원소를 넣어주고 시작

tok를 1번째 원소부터 돌면서 전과 같으면 cnt를 증가, 다르면 전까지 구한 cnt와 전의 token 즉 bf_t를 zip 문자열에 추가해주고 cnt를 0으로 초기화해준다.

(cnt가 0이면 숫자는 추가하지 않는다, cnt를 추가할 때 내가 0부터 시작했었기 때문에.. 1을 추가해줬다.)

만약 마지막 원소라면 지금까지 구한 cnt와 token을 같은 과정으로 추가해준다.

1개로 쪼갤때까지 반복해주고, 가장 작은 숫자를 return 해준다.

for(int i=s.length()/2; i != 0; i--){
    vector<string> tok = tokenizing(s, i);
    string bf_t = tok[0], cur_t, zip;
    int cnt=0;
    for(int j=1; j<tok.size(); j++){
        cur_t = tok[j];
        if (bf_t == cur_t){
            cnt++;
        }else{
            if(cnt != 0) zip += to_string(cnt+1);
            zip += bf_t;
            cnt = 0;
        }           
        if(j+1 == tok.size()){
            if(cnt != 0) zip += to_string(cnt+1);
            zip += cur_t;
        }
        bf_t = cur_t;
    }
    if(answer >= zip.length()) answer = zip.length();
}