프로그래머스 공부 level2 -문자열 압축

문제를 잘못 이해 했습니다. 

문제를 천천히 잘 읽도록 하겠습니다.

그런데 문제의도와는 다르지만 비슷하게 단어 별로 압축법을 만들었습니다. 

예를들어

aabbccc

2a2b3c ->7개

abcabcdde

2abcdde->2개

abcdabcdeef

4abcdeef->4개

저는 이런식으로 최대로 압축한 갯수를 구했습니다.

보니까 문제의 의도에서는 압축했을때 문자열이 가장 줄수가 가장 적은 문장을 고르는거였습니다. 

 

200818

 해결함

 

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

코딩테스트 연습 - 문자열 압축 | 프로그래머스

해결 정답 200818

#include <string>
#include <vector>
#include<iostream>
#include <string.h>
#include <string>
#include<cstring>
using namespace std;
int Divide(string s,int count){
    vector<char>c;
     vector<char>str;
    string delS=s;
    string strm="";
   int confirm=1;
   int nor=s.length()%count;
    int totalNum=0;
   // cout<<nor;
  
    static int tmpCounts=s.length(); 
    for(int i=0;i<s.length();i=i+count){
        
    for(int j=i;j<count+i;j++){
         if(s[j]!='!'||s[j]!=' '){
             
               
               c.push_back(s[j]); //비교 데이터 push
               totalNum++;
         
         }
      
      
      
    }
       // cout<<",";
   for(int j=i;j<count+i;j++){
           if(s[j+count]!='!'||s[j+count]!=' '){
               str.push_back(s[j+count]);// 원본 데이터 push
         }
   
   }
       
        
        
        bool bCheck=false;
        for(int j=0;j<c.size();j++){
        if(c[j]==str[j]){
             bCheck=true;
          }else{
             bCheck=false;
              break;
          }
         }
        
        if(bCheck){
            confirm++;
             
        }else if(!bCheck){
            if(confirm!=1){
             strm+=to_string(confirm);
             
            }
            
            tmpCounts=tmpCounts-c.size(); //현재 나눠준 범위가 넘어갔는지 체크
                                          //ex) 10을 3으로 나누면 1개가 남아서 한번더 3으로 나눌때
                                          // 333 +1  인데 여기서 c size 는 문자열과 관계없이 쓰레기값이 들어감
                                          //그래서 3 3 3 3으로 들어가 마지막 2자리가 쓰레기값이 들어감 
                                          // 이걸 없애기 위해 전체 길이를 구해서 c가 카운팅 될때 제거해서 음수값이 
                                          // 나오면 범위가 넘어간거여서 strm 값 입력시 3 3 3 1 이 들어가도록 +ns값을 넣어준다
          //  cout<<endl;
            //cout<<"c.size()"<<c.size()<<",";
            cout<<"tmpCounts"<<tmpCounts<<",";
          int ns=0;
          if(tmpCounts<0){
              ns=tmpCounts;
          }  
            
          for(int j=0;j<c.size()/confirm+ns;j++){ // confirm비교데이터의 중복데이터를 제거 하기위해 
                                                   //confirm 즉 현재 나눠지는 갯수로 나눠서 
                                                 //넣어줌 현재 c는 비교 데이터를 가지고 잇어서 중복데이터가 잇음
                
                   strm+=c[j];
                  // tmpCounts++;
                        
                  
                    //cout<<c[j];
                  
               }
          //  cout<<",";
        
          
            confirm=1;
           
            str.clear();//비교 원본 끝난 pop
            c.clear();//비교 끝난 pop
        }
     //   cout<<",";
     
    }
    cout<<endl;
  
    for(int i=s.length()-nor;i<s.length();i++){
       // strm=strm+s[i];
        str.clear();//비교 원본 끝난 pop
        c.clear();//비교 끝난 pop
    }
    
    
 
    
       fflush(stdin);
   
       if(strm!=""){
      //   cout<<"strm:"<<strm;  
        //  cout<<endl;
        
    
        
            }
     // cout<<"strm:"<< strm.length(); 
  tmpCounts=s.length();
   return strm.length();
}

int solution(string s) {
    int answer = 0;
    int min=Divide(s,1);
    for(int i=2;i<s.length()/2+1;i++){
       int tmp;
        tmp=Divide(s,i);
        if(tmp<=min){
            min=tmp;
        }
        
    }
    
    answer=min;
    
  //  if(s.length()%2==1)
        //answer=s.length();
    
    return answer;
}

상당히 어려웟다 그래도 일단 리뷰 하려한다 내코드여서 효율성은 좋은지 잘모르겟다

일단 통과는햇으니 천천히 해보자 

 

필자는 기본적으로 이걸 나눠서 생각했다

int min=Divide(s,1);
    for(int i=2;i<s.length()/2+1;i++){
       int tmp;
        tmp=Divide(s,i);
        if(tmp<=min){
            min=tmp;
        }
        
    }

그래서 재귀함수를 이용하였고

 

설명하자면 Divide 함수에 이렇게 나눠서 분배햇다 abcdefg는 예시이다.

for(int i=0;i<s.length();i=i+count)

여기서 count는 내가 나눠준 갯수이다.

즉 한글씩 나누는 거라면 1이 들어가고 두글자씩이면 2가 들어간다. .... 결국 재귀 돌리는 for문의 절반으로 나누는거다

즉 8글자를 나눌때 최종적으로 count는 4로 해서 나누는것 까지한다.

 

여기선 미리 비교해줄 테이터를 뽑는다 즉 내가 맘대로 다루기 편하도록 만들기 위해서 stack 공간에 미리 나눠둔 글자만 따로 저장한다 예를들어 한글자씩이면 count에 따라 한글자 세글자면 카운터는 세번돈다. 

그럼 세글자가 저장된다.

for(int j=i;j<count+i;j++){
         if(s[j]!='!'||s[j]!=' '){
             
               
               c.push_back(s[j]); //비교 데이터 push
               totalNum++;
         
         }
      
      
      
    }
       // cout<<",";
   for(int j=i;j<count+i;j++){
           if(s[j+count]!='!'||s[j+count]!=' '){
               str.push_back(s[j+count]);// 원본 데이터 push
         }
   
   }
       

  bCheck는 문자열 검사하는 bool이다 즉 true면 confim++( 압축된 갯수) 이고 아니면 false로 반환된다. 

즉 한글자씩이면 true false만 가능하지만 만약 세글자면 true,true ,false면 이미 이 세글자의 비교에선 틀린거여서 더이상 for문이 돌지 않고 같지않는 단어로 판단한다. 

더이상 같지 않는단어와 이미 압축된 갯수가 1이상이면 strm+=to_string(confirm);  숫자를 먼저 string 변환하여 넣어준다

 

for문은 글자의 크기이다 즉 세글자면 세번 네글자면 네번이 for문으로 돈다

 

bool bCheck=false;
        for(int j=0;j<c.size();j++){
        if(c[j]==str[j]){
             bCheck=true;
          }else{
             bCheck=false;
              break;
          }
         }
        
        if(bCheck){
            confirm++;
             
        }else if(!bCheck){
            if(confirm!=1){
             strm+=to_string(confirm);
             
            }
            
            tmpCounts=tmpCounts-c.size(); //현재 나눠준 범위가 넘어갔는지 체크
                                          //ex) 10을 3으로 나누면 1개가 남아서 한번더 3으로 나눌때
                                          // 333 +1  인데 여기서 c size 는 문자열과 관계없이 쓰레기값이 들어감
                                          //그래서 3 3 3 3으로 들어가 마지막 2자리가 쓰레기값이 들어감 
                                          // 이걸 없애기 위해 전체 길이를 구해서 c가 카운팅 될때 제거해서 음수값이 
                                          // 나오면 범위가 넘어간거여서 strm 값 입력시 3 3 3 1 이 들어가도록 +ns값을 넣어준다
          //  cout<<endl;
            //cout<<"c.size()"<<c.size()<<",";
            cout<<"tmpCounts"<<tmpCounts<<",";
          int ns=0;
          if(tmpCounts<0){
              ns=tmpCounts;
          }  

 

 

그다음 divide 함수 맨 위에 static int tmpCount=s.length(); 가 있는데 

tmpCounts=tmpCounts-c.size();

해준 이유가 글자수 때문이다 예를들어 10글자를 3글자씩 나눠서 압축할때

3 + 3+ 3+1  하고 한글자가 부족하다 이때 문자열은 관계없이 쓰레기 값이 들어가서 

이를 방지하기위해서 tmpCounts 미리 문자열을 받아서 현재 10 -3 =7 다음 7-3=4 다음  4-3=1 다음 1-3=-2 

이런식으로 음수를 측정합니다.

음수가 나왓으면 문자열을 초과한거로 인지합니다.

 

초과한 ns에 음수 -2를 넣어줍니다.  

원래의  tmpCounts 양수면 ns는 0입니다.

  if(tmpCounts<0){
              ns=tmpCounts;
          }  
            

넣어주 c.size()는 현재 비교 문자 갯수 confirm 압축 갯수입니다. ns는 글자 초과시 현재 길이를 뺴줍니다.

예를들어 1글자 비교만하면되는 3 + 3+ 3+1 맨마지막c.size()는3이고

두글자가 쓰레기값 즉  ex)a, 쓰레기 값  , 쓰레기값 confim 은 당연히 1이고요 그럼 3-2(ns) 1만 나오게 됩니다.

그리고 최종 string strm에 입력 해줍니다.

confim 다시 1로 초기화 str,c도 초기화해줍니다. tmpCounts도 초기화 strm을 길이를 리턴합니다.

 

for(int j=0;j<c.size()/confirm+ns;j++){ // confirm비교데이터의 중복데이터를 제거 하기위해 
                                                   //confirm 즉 현재 나눠지는 갯수로 나눠서 
                                                 //넣어줌 현재 c는 비교 데이터를 가지고 잇어서 중복데이터가 잇음
                
                   strm+=c[j];
                  // tmpCounts++;
                        
                  
                    //cout<<c[j];
                  
               }
          //  cout<<",";
        
          
            confirm=1;
           
            str.clear();//비교 원본 끝난 pop
            c.clear();//비교 끝난 pop
        }
        
        tmpCounts=s.length();
   return strm.length();

여기서 어려웟던점은 쓰레기값들이 들어갈때 처리하는 방법이었습니다. 

 

 

 

201017

 

훨씬 간단하게 해결 하였고 

아이디어는 지난번과 비슷함

깊이 우선 탐색과 정렬 그리고 스택을 조합함 

마지막 예외처리가 좀 중요한데 

문자열 비교이기 때문에 하나도 안들어가는 경우랑 

그리고 문자열이 하나만 들어가는 경우이다. 

이것만 주의하면됨 기본적인 아이디어는 지난번과 비슷함 

단지 좀더 효율적으로 잘짠듯하다 

#include <string>
#include <vector>
#include<iostream>
#include <string.h>
#include<cstring>
#include<algorithm>
using namespace std;

int func(string s,int size,int confirm,string totalStr){
    //cout<<endl;
    if(s.size()<size){
        if(s.size()>0){
            for(int i=0;i<s.size();i++){
            totalStr+=s[i];
                }
        }
     //   cout<<size<<":"<<totalStr;
        return totalStr.length();
    }
    
    string str1="";
     string str2="";
   for(int i=0;i<size;i++){
       str1+=s[i];
   }
    
    for(int i=size;i<s.size();i++){
       str2+=s[i];
   }
   // cout<<str1;
    //cout<<endl;
    //cout<<str2;
    //cout<<endl;
    
    
       
    if(strncmp(str1.c_str(),str2.c_str(),size)==0){
        confirm++;
    }else{
        if(confirm>1){
            totalStr+=to_string(confirm);
        }
        totalStr+=str1;
        confirm=1;
        
    }
         
     
    for(int i=0;i<size;i++){
        s.erase(s.begin());
    }
    
  //
    return func(s,size,confirm,totalStr);
}
int solution(string s) {
    int answer = 0;
    int size=s.size();
    vector<int>saveData;
 //   cout<<size;
    string totalStr="";
    if(s.size()==0){
        return 0;
    }
    if(s.size()==1){
        return 1;
    }
    for(int i=0;i<size/2;i++){
        
        int tmpStr=func(s,i+1,1,totalStr);
        saveData.push_back(tmpStr);
            cout<<endl;
       // cout<<"=======================";
        // cout<<endl;
         //cout<<"=======================";
          //  cout<<endl;
    }
    sort(saveData.begin(),saveData.end());
    //cout<<saveData[0];
    answer=saveData[0];
    
    return answer;
}