프로그래머스 / 문자열 압축

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

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

 

문제 요약 >

문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현할 수 있다. 압축할 문자열 s가 주어질 때, 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 구하자.

 

풀이 >

처음엔 문제의 의도를 파악하기 조금 어려웠는데, 예시 5번을 보고 이해를 할 수 있었다. 문자열은 제일 앞부터 정해진 길이만큼 자를 수 있다는 것이 포인트이다.

 

aabbaccc

이러한 문자열이 주어지는 경우, 1씩 잘라서 압축하는 경우 결과가 2a2ba3c이고, 길이는 7이다.

만약 2씩 잘라서 압축하는 경우에는 aa, bb, ac, cc로, 중복되는 부분이 없기 때문에 압축할 수 없다.

 

xababcdcdababcdcd

이러한 문자열이 주어지는 경우, 1씩 잘라서 압축하는 경우 결과가 xababcdcdababcdcd로, 압축되지 않고 길이는 17이다.

2씩 잘라서 압축하는 경우에는 xa, ba, bc, dc, da, ba, bc, dc, d로, 중복되는 부분이 없기 때문에 압축할 수 없다.

 

내가 짠 코드는 아래와 같은데, splitCount는 앞에서부터 얼마나 자를지 ㅡ 그렇기 때문에 for문에서 1씩 늘어난다ㅡ

dupCount는 중복된 부분의 개수, len은 결과물의 길이를 뜻한다.

 

aabbaccc를 예로 들면, splitCount가 1인 경우

prevTempStr은 문자열을 앞에서부터 1만큼 자른 a, curTempStr은 그 다음 1만큼인 a이고

두개를 비교해서 같은 경우, 그 다음에 또 a가 나오는지 확인하기 위해 바로 resultStr에 추가하지 않고 dupCount를 2로 만든다.

그 후 한 칸 이동하며 prevTempStr은 a, curTempStr은 b가 되고

두개가 다른 문자열이기 때문에 "dupCount" "prevTempStr"을 resultStr에 추가하고 dupCount를 초기화한다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(string s) {
    int splitCount = 1, dupCount = 0, len = 0, answer = s.size();
    string prevTempStr, curTempStr, resultStr;
    
    for (int i = splitCount; i <= s.size() / 2; i++, splitCount++)
    {
        resultStr = "";
        dupCount = 0;
        prevTempStr = s.substr(0, i);
        
        for (int j = splitCount; j < s.size(); j += splitCount)
        {
            curTempStr = s.substr(j, splitCount);
            if (curTempStr.compare(prevTempStr) == 0) // 중복 문자열 발생
            {
                if (dupCount == 0) dupCount += 2; // 처음인 경우
                else dupCount++; // 이미 dupCount가 존재하는 경우 1씩 증가
            }
            else // 중복 문자열이 아닌 경우
            {
                if (dupCount == 0) resultStr += prevTempStr; // 단순 write
                else
                {
                    resultStr += to_string(dupCount); // 중복된 횟수를 표기하여 write
                    resultStr += prevTempStr;
                    dupCount = 0;
                }
            }
            prevTempStr = curTempStr;
        }
        
        // for문이 끝난 후, 남아있는 문자열을 write
        if (dupCount == 0) resultStr += prevTempStr;
        else
        {
            resultStr += to_string(dupCount);
            resultStr += prevTempStr;
        }
                            
        len = resultStr.size();
        answer = min(len, answer);
    }
    return answer;
}