프로그래머스 - Level 1 문자열 압축(카카오 2020공채 문제)

pa324·2019년 11월 24일
0

문제

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

풀이

  • 브루트 포스로 해결할 수 있는 문제이다. 브루트 포스는 문제를 해결하기 위해 모든 가능한 경우의 수를 직접 조합 및대입하여 해결하는 방법이다.(집의 비밀번호가 9999라면, 0001~9999까지 하나하나 입력해서 9999를 찾아내는 것)

  • 문자열이 주어졌을때, 1자리씩 압축하는 경우부터 n/2까지 압축하는 경우까지 모두 구해서 가장 길이가 짧은 것을 선택하면 된다.

    • 길이가 10인 문자열을, 5보다 큰 값으로 압축할 수 없다.(n/2)

코드

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int len = s.size();
    int answer = len;
    
    for(int i = 1; i <= (len/2); i++) {
        
        string result = "";
        string temp = s.substr(0,i);
        int count = 1;
        
        
        for(int j = i; j <= len; j+=i) {
            if(temp == s.substr(j,i)) {
                count++;
            }
            else {
                if(count == 1) {
                    result += temp;
                }
                else {
                    result += (to_string(count) + temp);
                }
                temp = s.substr(j,i);
                count = 1;
                
            }
        }
        
        if(len / i != 0) {
            result += s.substr((len/i) * i);
        }
        if(answer > result.size()) answer = result.size();
        
    }
    
    return answer;
}
profile
안녕하세요

0개의 댓글