[틀림] 프로그래머스 문자열 압축 // 문자열, 구현

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

프로그래머스

* 풀이

• split해서 vector에 넣음
• 쌍으로 완탐
• 이때, count 변수가 중요한 역할
  • skip할 갯수
  • 같은패턴이 몇번나왔는지 

#include <bits/stdc++.h>

using namespace std;

int ret=987654321;

vector<string> split(string s, int dan){
    vector<string> ret;
    for(int i=0;i<s.size();){
        ret.push_back(s.substr(0+i,dan));
        i+=dan;
    }
    return ret;
}

int solution(string s) {
    int n = s.size();
    int ret = n; // 전역변수 대신 지역변수로 사용
    
    // 단위 : 1~ 전체
    for(int dan=1;dan<=s.size();++dan){
        int answer = s.size();
        vector<string> v = split(s,dan);
        
        int i = 0;
        while(i < v.size()) {
            string tmp = v[i];
            int count = 1; // 초기값=자기자신 : 1
            
            // 같은 패턴이 연속되는지 확인
            while(i + count < v.size() && tmp == v[i + count]) {
                count++;
            }
            
            // 반복된 패턴이 있는 경우
            if(count > 1) {
                // (패턴 길이 × 반복횟수) - (압축된 길이: 패턴 길이 + 숫자 길이)
                answer = answer - (dan * count) + (dan + to_string(count).length());
            }
            
            // 다음 검사할 인덱스로 이동
            i += count;
        }
        
        ret = min(ret, answer);
    }
    return ret;
}

 

* 오답풀이

• for문의 i++과 skip 로직이 꼬여서 너무복잡
• 10개이상 패턴이 반복되는 경우 반례
  • ex) 10 abc -> to_string(cnt).size 만큼 빼야하는데 , 무조건 -1만 했엇음
• 개선할점
  • i++이 아니라면 for문대신 while 문
  • 숫자가 나오는 문제의경우, 두자리넘어갈때를 예외케이스로 생각

#include <bits/stdc++.h>

using namespace std;

int ret=987654321;

vector<string> split(string s, int dan){
    vector<string> ret;
    for(int i=0;i<s.size();){
        ret.push_back(s.substr(0+i,dan));
        i+=dan;
    }
    return ret;
}

int solution(string s) {
    int n = s.size();
    // 단위 : 1~ 전체
    for(int dan=1;dan<=s.size();++dan){
        int answer = s.size();
        vector<string> v = split(s,dan);
        
        // for(auto s : v){
        //     cout<<s<<" ";
        // }
        for(int i=0;i<v.size()-1;++i){
            string tmp = v[i];
            int flag=0;
            for(int j=i+1;j<v.size();++j){
                if(tmp!=v[j]) {
                    // i++;
                    break;
                }
                flag=1;
                answer-=dan;
                i++; // for skip
            }
            if(flag) answer++; //앞에 숫자 달아주기
        }
        // cout<<answer<<"\n";
        ret = min(ret,answer);

    }
    return ret;
}