Programmers - 문자열 압축

프로그래머스 - 카카오 2020 - 문자열 압축

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

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

---

문제

• 압축할 문자열 s를 1개 이상 단위 문자열로 잘라 압축하여 가장 짧은 것의 길이를 return 하라

• ex) aabbaccc -> 2a2ba3c 로 압축할 수 있다.

• ex) ababcdcdababcdcd -> 2ab2cd2ab2cd, 2ababcdcd 뒤에 것이 더 짧게 압축 가능하다.

조건

• 1 <= s.length() <= 1000

• s는 알파벳 소문자

풀이

• 1~length/2까지 압축의 경우를 모두 해본다.

• func compress(문자열, 개수) -> length 를만든다.

• length 가 가장 작은 것 리턴

코드 (C++)

#include  
#include  
#include

using namespace std;

int compressStr(string str, int num) {  
  string result = "";  
  string cmpStr = str.substr(0, num);  
  int index = num;  
  int count = 1;

  // num만큼 index를 이동하면서 비교해 주었다.
  while(index <= str.length()-num) {
      string tempStr = str.substr(index, num);
      if(cmpStr == tempStr) {
          count++;
      }
      else {
          if(count != 1) {
              result += to_string(count) + cmpStr;
              count = 1;
          } else {
              result += cmpStr;
          }
          cmpStr = tempStr;
      }
      index += num;
  }

  // 마지막 처리
  if(count != 1) {
      result += to_string(count) + cmpStr + str.substr(index);
      count = 1;
  } else {
      result += cmpStr + str.substr(index);
  }

  return result.length();
}

int solution(string s) {  
  // 가장 시작은 압축되지 않은 문자열의 길이 s.length이다.  
  int answer = s.length();

  for(int i=1; i<=s.length()/2; i++) {
      int length = compressStr(s, i);
      if(answer > length) answer = length;
  }

  return answer;
}  

---

주의 사항

• 문자열 문제를 풀 때 인덱스를 이용해서 비교하거나 원하는 값을 찾는 경우 마지막 인덱스가 포함이 안되는 것에 주의하자.
• 이 문제는 길이만 필요해서 굳이 문자열을 만든 다음 길이를 뽑아내지 않아도 된다. (다른 사람 풀이에는 길이만 이용)
• 시간이 된다면 3~4개 정도 테스트 케이스를 더 만들어서 확인을 해보는 것이 좋겠다.