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

 

 

 

https://programmers.co.kr/learn/courses/30/lessons/60057?language=cpp

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

 

 

 

이번 문제는 완전 탐색 문제였습니다.

 

 

 

 

《문제 풀이》

 

1. 문자열 s를 압축할 수 있는 최대 길이는 s 길이의 절반임 ★

2. string의 substr() 함수를 이용하여 문자열 비교

3. 비교하는 문자열과 현재 문자열이 

     ☛ 같다면 cnt++

     ☛ 같지 않다면 temp 문자열에 cnt와 비교하는 문자열을 더해줌 (cnt는 cnt > 1 인 경우에만 더해줌)

4. 압축한 문자열이 answer보다 짧다면 answer을 압축한 문자열의 길이로 갱신 

 

 

 

 

 

《C++ 코드》

 

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = s.size();
    
    for (int i=1; i<=s.size() / 2; i++) {
        int cnt = 1;
        string temp = "";
        string compareStr = s.substr(0, i);
        
        for (int j=i; j<s.size(); j+=i) {
            string currentStr = s.substr(j, i);
            if (compareStr == currentStr) cnt++;
            else {
                if (cnt > 1) temp += to_string(cnt);
                temp += compareStr;
                compareStr = currentStr;
                cnt = 1;
            }
        }
        
        if (cnt > 1) temp += to_string(cnt);
        temp += compareStr;
        answer = answer > temp.size() ? temp.size() : answer;
    }
    
    return answer;
}

 

 

 

 

 

프로그래머스 - 정답 화면