[문자열] 문자열 압축 - 2020 카카오 블라인드 채용

주의할 점

이 문제를 이해할 때 놓치기 쉬운 포인트가 있는데, 문자열을 제일 앞부터 고정된 길이만큼 잘라야 하는 것이다.

즉, "ababcdcdababcdcd" 문자열을 2개 단위로 자르려면 다음과 같이 잘라야 하는 것이다.

-> ab/ab/cd/cd/ab/ab/cd/cd

필자는 이 조건을 놓친 덕에 총 2문제를 풀게 되었다. 이 조건 없는게 더 압축 효율이 좋을텐데...

어쨌든, 문자열을 제일 앞부터 자르지 않아도 되는 경우에 해당하는 소스코드는 맨 아래에 첨부하였다.

 

 

해결 방법

본 문제로 넘어가서, 필자는 다음과 같은 방법으로 문제를 해결했다.

문자열을 1개 단위부터 s.length()/2개 단위까지 자른 모든 경우를 따져봐서, 압축된 각 문자열들의 최솟값을 구했다.

그리고, 문자열을 a개 단위로 자르는 경우마다 다음과 같은 3가지 과정이 필요했다.

step1 : 매개변수로 들어온 문자열을 a개 단위로 잘라서 vector에 넣는다.

step2 : vector의 현재 요소와 다음 요소를 비교해서 일치하다면, 그 다음 요소와도 계속해서 비교한다. 이렇게 압축이 가능해질 때마다 압축 횟수를 1씩 카운트하면서 문자열의 길이를 a씩 줄여준다.

step3 : 압축이 더이상 불가능해질 때는 압축 횟수가 확정된다. 압축 횟수도 압축된 문자열에 포함시켜야 하며, 압축 횟수의 자리수까지 고려해야 한다. 예를 들어, 압축 횟수가 11회라면 문자열의 길이에 2를 추가해야 하는 것이다.

 

 

소스 코드

#include <string>
#include <string.h>
#include <vector>
#include <iostream>

using namespace std;
vector<string> v;
int ans=9999;


int solution(string s) {
  int slen=s.length();
  if(slen==1) return 1;
    
  for (int i=1;i<=slen/2;i++) {
    int len=slen; // len : step의 값에 따른 압축된 문자열의 길이
    int step=i; // step : 문자열을 압축하는 단위
    int p=0; // p : 현재의 위치
    
    for (int j=0; j<slen; j+=step) {
      if(j+step<=slen) v.push_back(s.substr(j, step));
    }
    int vsize=v.size();
        
    while(p<vsize) {
      int found=0;
            
      while(1) {
        if(p==vsize) { // 압축중에 끝나는 경우
          if(found) len+=to_string(found+1).length(); //압축된 정도를 나타내는 숫자 추가
          break;
        }
        if(v[p]==v[p+1]) { // 압축이 가능한 경우
          len-=step;
          p++;
          found++;
        } else { // 더 이상 압축이 불가능한 경우
          if(found) len+=to_string(found+1).length();
          p++;
          break;
        }
      }
    }
    ans=min(ans, len);
    v.clear();
  }
  return ans;
}


int main() {
  string str;
  cin >> str;
  cout << solution(str);
}

 

28개 테스트케이스 모두 정답

 

 

+) 추가

문자열을 제일 앞부터 잘라야 하는 조건이 없다면, 다음과 같이 구현할 수 있다.

#include <string>
#include <string.h>
#include <vector>
#include <iostream>
using namespace std;
int ans=9999;

int solution(string s) {
  int slen=s.length(); // slen : 매개변수로 들어온 문자열의 길이
  if(slen==1) return 1;
  int len, step, p;
  
  for(int i=1;i<=slen/2;i++){
    len=slen; // len : step의 값에 따른 압축된 문자열의 길이
    step=i; // step : 문자열을 압축하는 단위
    p=step-1; // p : 현재의 위치
    
    while(p+step<slen){
      string sub=s.substr(p-step+1, step);
      int found=0;
      
      while(1){
        if(p+step>=slen) { // 압축중에 끝나는 경우
          if(found) len+=to_string(found+1).length(); //압축된 정도를 나타내는 숫자 추가
          break;
        }
        if(s.substr(p+1, step)==sub){ // 압축이 가능한 경우
          len-=step;
          p+=step;
          found++;
        }
        else { // 더 이상 압축이 불가능한 경우
          if(found) len+=to_string(found+1).length();
          p++;
          break;
        }
      }      
    }
    ans=min(ans, len);
  }  
  return ans;
}


int main(){
  string str;
  cin >> str;
  cout << solution(str);
}