Programers : 문자열 압축 (2020 KAKAO BLIND RECRUITMENT)

문자열 압축

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 11:38 시작
int solution(string s) {
    int answer = 0;
    // 문자열이 n일때  1 ~ n/2개 단위로 자를때 까지 구해서 최솟값을 찾아야 한다 (홀수포함)
    int until = s.length()/2;
    vector<string> arr(until, "");
    vector<int> result;
    /* 문자열이 1개일 때 1로 바로 리턴 - 예외처리 */
    if(s.length() == 1) return 1;

    /* slice는 문자를 자르는 단위! */
    for(int slice=1;slice<=until;slice++)
    {
         /* 비교할 기준이 되는 문자의 반복문 */ 
        for(int i=0;i<s.length();)
        {
            int cnt=1;
            /* 비교되는 문자! */
            string fix = s.substr(i,slice);
            /* 비교할 대상이 되는 문자의 반복문 - 마지막 요소를 마저 추가하기 위해 +slice 처리 */
            for(int j=i+slice;j<s.length()+slice;j+=slice)
            {
                string comp;
                if(j < s.length()) comp = s.substr(j,slice); 
                else comp = " ";
                if(fix == comp) cnt++;
                else if(cnt > 1){
                    string tmp = to_string(cnt) + fix;
                    arr[slice-1] += tmp;
                    break;
                }else {
                    arr[slice-1] += fix;
                    break;
                }
            }
            i += cnt*slice;
        }
    }

    for(auto a:arr) 
        result.push_back(a.length());

    answer = *min_element(result.begin(), result.end());
    return answer;
}
  • 문자열이 n일때에 [ 1 ~ n/2개 ]의 단위로 자를 때 까지 개수를 구한 뒤 최소를 구해야 함
  • 3중 for문으로 구조가 구성됨
    1) slice for문 : 1 ~ n/2개 단위로 자르는 큰 틀
    2) 비교 할 기준이 되는 문자 for문
    3) 비교 할 대상이 되는 문자 for문
  • 예외로 문자열이 1일 때 바로 return 처리를 해주어야 한다

좋은 웹페이지 즐겨찾기