프로그래머스[programmers] - 문자열 압축(C++)[LV2]

📕문제

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

프로그래머스

---

🔎문제 풀이

문자열을 이용한 구현 문제입니다.

문제가 굉장히 길지만, 요약하자면 주어진 문자열을 N개 단위로 잘라서, 가장 짧은 문자열로 만들 자입니다.

그러면 각 N개마다 자른 문자열의 길이를 비교하면 되는 문제입니다.

여기서 중요한 점은 문자열의 길이가 N이라면, N/2까지만 검사합니다.

만약 N/2를 넘어서 자르게 된다면 당연히 압축이 안 되겠죠?? 

그래서 저는 1개~N/2개까지 잘랐습니다.

 

문자열의 처음 시작점부터 N 개씩 잘라서 기준 문자열로 정합니다.

기준 문자열을 정했으므로, N개부터 탐색을 시작하면 됩니다.

(0, N)까지의 범위와 (N, N)까지의 범위를 비교합니다.

만약 같다면 압축이 가능하다는 뜻입니다.

예를 들어서 설명해 드리겠습니다.

---

문자열 : ABCABCABCD가 있을 때, 3개 단위로 자른다고 가정하겠습니다.

설명을 위해서 기준 문자열을 t라고 하고, 탐색문자열을 s라고 하겠습니다.

1. t = 시작점부터 3개까지인 ABC가 될 것입니다.
2. s = 시작점 + 3인 4부터 6까지인 ABC가 될 것입니다.
3. s를 구한 뒤, t와 s를 비교합니다.
4. t와 s는 같기 때문에 압축이 가능합니다. 다음 탐색에서 또 같은 문자열의 패턴이 나올 수 있기 때문에 
   같다는 표시인 count를 1 증가시킵니다.
5. s = 다음 문자열은 이제 7부터 10까지인 ABC가 될 것입니다.
6. 다시 3번부터 시작합니다.
7. t와 s를 비교해서 같기 때문에 count를 1 증가시키고 다음 문자열을 탐색합니다.
8. 다음 문자열은 D하나이기에 다르고 ABC와 count를 더한 3 ABCD가 압축한 문자열이 될 것입니다.

핵심내용은 t와 s가 같다면 count를 증가시켜서 압축을 시작하고 달라지면, 압축한 문자열과 count를 더해줍니다.

 

위 예시는 조금 쉬운 경우라서 다른 예시를 들어보겠습니다.

---

문자열 aabbacc가 있을 때, 2개 단위로 자른다고 가정하겠습니다.

1. t=시작점부터 2개인 aa가 될 것입니다. s= 3번~4번인 bb가 될 것입니다.
2. t와 s를 비교했는데, t와 s는 다르기에 t를 최종문자열에 더하고, t를 s로 바꿔줍니다.
   이전 t는 역할을 다 했기 때문에 다음 문자열을 탐색할 때 새로운 t를 사용하겠다는 뜻입니다. 
3. t=bb이고, s = 5번~6번인 ac가 될 것입니다.
4. 2번 과정을 진행하는데, t와 s가 다르기에, 최종 문자열을 t로 더하고, t=ac가 될 것입니다.
5. 여기서 6번부터 7번을 잘라야 하는데,  문자열의 길이가 넘기 때문에 
   최종문자열에 6번 문자인 c를 추가적으로 더해줍니다.

 

💡요약

t와 s가 같을 때는 압축시켜서 다음 문자열을 계속 검사하다가, 달라지면 더해주고, t를 s로 바꿔주고 검사를 주욱 진행합니다.
다를 경우는 t를 더하고, s를 t로 바꿔줍니다.그러다가 더 이상 자르지 못할 경우 해당 범위부터 문자열의 끝까지 최종 문자열에 더해줍니다.

 

한 가지 주의할 점은 문자열의 길이가 1인 경우를 따로 처리해 줘야 테스트케이스에서 걸리지 않습니다.

 

예시가 조금 부족할 경우 전체 코드와 주석을 읽으면 될 거 같습니다.

---

코드

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

using namespace std;
int answer = 1001;
int Size=0;
int funct(string s, int len){
    int result=0,count=0;
    string temp = s.substr(0,len); //0부터 len개수만큼 끊음.
    string ss="";
    bool flag = true;
    if(len==s.size()/2 && s.size()%2==0){ //딱 절반일때.
        if(temp==s.substr(len,len)) //같으면
            return len+1;
        else //다르면
            return s.size();
    }
    else{
        for(int i=len; i<=s.size();i+=len){
            if(temp!=s.substr(i,len)){ //미리 자른 문자열과 압축한 문자열이 다르다면.
               if(count==0) //앞에 저장된 문자열이 없다면
                   ss+=temp;
                else //저장된 문자열이 있다면 압축해서 저장함.
                    ss+=to_string(count+1)+temp;
                temp=s.substr(i,len);//탐색문자열을 변경함.
                count=0; //count값 초기화
            }
            else //같다면.
                count++,flag=false;
            if(i+len>s.size()) //넘을때
                ss+=s.substr(len,s.size()-i);
        }        
    }
    return ss.size();
}
int solution(string s) {
    Size=s.length();
    if(Size==1)
        return s.size();
    for(int i=1; i<=Size/2; i++) //절반까지 검사. 절반을 넘어가는 경우는 생각할 필요가 없음
        answer=min(answer,funct(s,i));
    return answer;
}