[프로그래머스] 문자열 압축

1) 문제

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

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

문자를 1개 단위로 잘랐을 때

aabbaccc -> 2a2ba3c

문자를 8개 단위로 잘랐을 때

ababcdcdababcdcd -> 2ababcdcd

문자를 3개 단위로 잘랐을 때

abcabcdede -> 2abcdede

문자를 2개 단위로 잘랐을 때

abcabcdede -> abcabc2de

 

문자열을 잘라 가장 짧은 것의 길이를 return

 

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

**문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.

 

2) 풀이

 

문자열을 부분집합으로 나누어서 전체 문자열을 돌면서 카운팅한다.

좀 더 구체적으로 말하면

이전 부분집합과 현재 부분집합을 따로 저장해두고

현재 부분집합이 이전 부분집합과 동일하면 카운트 증가 저장

현재 부분집합이 이전 부분집합과 다르면 카운트 string 변환하고 이전 부분집합 append

 

3) 코드

int solution(string s) {
    int answer = 1000000;
    int length = s.length();
    if(length == 1) return 1;
    //1부터 증가하면서
    for(int divisor=1; divisor<length; divisor++) {
        string answerString = "";
        pair<string, int> preSubset {"", 0};
        //약수로 문자열 나누기
        for(int i=0; i<length; ) {
            // subset : 나뉜 문자열
            string subset = "";
            int subLength = i+divisor > length ? length : i+divisor;
            for(int j=i; j<subLength; j++) {
                subset += s[j];
            }

            //cout << "div : " << divisor << ", i : " << i << ", subset : " << subset << endl;
            // 같은 문자열 counting
            if(i == 0) {
                preSubset = {subset, 1};
                //cout << "first" << endl;
            }
            else if(preSubset.first == subset) {
                preSubset.second += 1;
                //cout << "2. " << preSubset.first << "  " << preSubset.second << endl;
                string prefix = "";
                if(i==length-divisor) {
                    if(preSubset.second > 1) {
                        prefix = to_string(preSubset.second);
                    }
                    answerString += prefix.append(preSubset.first);
                    preSubset = {subset, 1};
                }
            }
            else if(preSubset.first != subset){
                //cout << "3. " << preSubset.first << "  " << preSubset.second;
                string prefix = "";
                if(preSubset.second > 1) {
                    prefix = to_string(preSubset.second);
                }
                answerString += prefix.append(preSubset.first);
                if(subset.length() < preSubset.first.length()) {
                    answerString += subset;
                }
                preSubset = {subset, 1};
                //cout << "/ newSubset : " << preSubset.first << endl;
                if(i+divisor == length) {
                    answerString += preSubset.first;
                }
            }

            //cout << "answerString : " << answerString << endl;
            //cout << "i+div : " << i+divisor << "/ diff : " << length-i << endl;
            //cout << endl;
            //다음 subset 계산을 위한 index 처리
            if(i+divisor>length) {
                i+=length-i;
            }
            else {
                i+=divisor;
            }
        }
        //cout << "length : " << answerString.length() << endl;
        answer = answer < answerString.length() ? answer : answerString.length();

    }
    return answer;
}

 

4) 정리

 

처음에 문자열이 남는 문자 없이 정확하게 나눠어야 하는 줄 알고 시간을 허비했다...

그래도 전체적인 알고리즘이 변경되는 문제는 아니어서 금방 해결되긴 했다.

전체적으로 코드가 마음에 들진 않는다.

좀 더 효율적으로 수정할 수 있을 것 같다.

다른 풀이를 좀 보고 보완할 내용을 덧붙일 예정이다.